問題描述

張超來到了超市購物。

每個物品都有價格，正好趕上商店推出促銷方案。就是把許多東西一起買更便宜(保證優(yōu)惠方案一定比原價便宜)。物品要買正好的個數(shù)，而且不能為了便宜而買不需要的物品。

張超拿到了優(yōu)惠方案，和需要購買的物品清單，當然想求出最小的花費。他是信息學選手，自然地想到寫個程序解決問題。

輸入格式

第一行促銷物品的種類數(shù)(0 <= s <= 99)。

第二行..第s+1 行每一行都用幾個整數(shù)來表示一種促銷方式。

第一個整數(shù) n (1 <= n <= 5)，表示這種優(yōu)惠方式由 n 種商品組成。

后面 n 對整數(shù) c 和 k 表示 k (1 <= k <= 5)個編號為 c (1 <= c <= 999)的商品共同構(gòu)成這種方案。

最后的整數(shù) p 表示這種優(yōu)惠的優(yōu)惠價(1 <= p <= 9999)。也就是把當前的方案中的物品全買需要的價格。

第 s+2 行這行一個整數(shù)b (0 <= b <= 5)，表示需要購買 b 種不同的商品。

第 s+3 行..第 s+b+2 行這 b 行中的每一行包括三個整數(shù)：c ，k ，和 p 。

C 表示唯一的商品編號(1 <= c <= 999)，

k 表示需要購買的 c 商品的數(shù)量(1 <= k <= 5)。

p 表示 c 商品的原價(1 <= p <= 999)。

最多購買 5*5=25 個商品。

輸出格式

一個整數(shù)ans，表示需要花的最小費用

樣例輸入

2

1 7 3 5

2 7 1 8 2 10

2

7 3 2

8 2 5

樣例輸出

14

思路： 動態(tài)規(guī)劃 ?完全背包 變形

#include

#include

long?int?bj(long?int?a,long?int?b)

{?return?a

}

int?main()

{?long?int?s,i,j,j1,b,ans=0,dans=0,b1,b2,b3,b4,b5;

long?int?sn[101];//sn[i]第i種促銷種類的物品數(shù)

long?int?c[101][7],k[101][7],p[101],xc[7]={0},xp[7]={0},xk[7]={0};

long?int?dp[6][6][6][6][6];//dp[2][3][4][1][0]代表?當前第?1~5?個物品?分別?購2?3?4?1?0?件所需最少錢

long?h[6]={0};//h[i]?表示?i?號商品促銷數(shù)量

long?sbh[1001]={0};//標號表?鏈接?促銷序號和需買序號的橋梁

scanf("%ld",&s);

for(i=1;i<=s;i++)

{

scanf("%ld",&sn[i]);

for(j=1;j<=sn[i];j++)

scanf("%ld%ld",&c[i][j],&k[i][j]);

scanf("%ld",&p[i]);

}

scanf("%ld",&b);

for(i=1;i<=b;i++)

scanf("%ld%ld%ld",&xc[i],&xk[i],&xp[i]);

for(j=1;j<=b;j++)//初始化需求物品的數(shù)量?sbh[i]?代表需求品序號?存?需求數(shù)量

sbh[xc[j]]=j;

for(b1=0;b1<=xk[1];b1++)

for(b2=0;b2<=xk[2];b2++)

for(b3=0;b3<=xk[3];b3++)

for(b4=0;b4<=xk[4];b4++)

for(b5=0;b5<=xk[5];b5++)

if(b1*xp[1]+b2*xp[2]+b3*xp[3]+b4*xp[4]+b5*xp[5])dp[b1][b2][b3][b4][b5]=b1*xp[1]+b2*xp[2]+b3*xp[3]+b4*xp[4]+b5*xp[5];

dp[0][0][0][0][0]=0;?//初始化?原價購買

for(i=1;i<=s;i++)

{

for(j=1;j<=sn[i];j++)

if(xk[sbh[c[i][j]]]

if(j

for(j=1;j<=sn[i];j++)

h[sbh[c[i][j]]]=k[i][j];

for(b1=h[1];b1<=xk[1];b1++)

for(b2=h[2];b2<=xk[2];b2++)

for(b3=h[3];b3<=xk[3];b3++)

for(b4=h[4];b4<=xk[4];b4++)

for(b5=h[5];b5<=xk[5];b5++)

dp[b1][b2][b3][b4][b5]=bj(dp[b1][b2][b3][b4][b5],dp[b1-h[1]][b2-h[2]][b3-h[3]][b4-h[4]][b5-h[5]]+p[i]);

for(j=1;j<=sn[i];j++)

h[sbh[c[i][j]]]=0;

}

ans=dp[xk[1]][xk[2]][xk[3]][xk[4]][xk[5]];

printf("%ld\n",ans);

return?0;

}

總結(jié)

以上是生活随笔為你收集整理的购物打折C语言程序设计,算法提高 促销购物(动态规划+完全背包）-----------------C语言——菜鸟级...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。