小明系列故事——買年貨

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Time Limit: 5000/2000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)

Problem Description 春節將至，小明要去超市購置年貨，于是小明去了自己經常去的都尚超市。
　　剛到超市，小明就發現超市門口聚集一堆人。用白云女士的話說就是：“那家伙，那場面，真是人山人海，鑼鼓喧天，鞭炮齊呤，紅旗招展。那可真是相當的壯觀啊！”。好奇的小明走過去，奮力擠過人群，發現超市門口貼了一張通知，內容如下：
　　
　　值此新春佳節來臨之際，為了回饋廣大顧客的支持和厚愛，特舉行春節大酬賓、優惠大放送活動。凡是都尚會員都可用會員積分兌換商品，凡是都尚會員都可免費拿k件商品，凡是購物顧客均有好禮相送。滿100元送bla bla bla bla，滿200元送bla bla bla bla bla...blablabla....
　　
　　還沒看完通知，小明就高興的要死，因為他就是都尚的會員啊。迫不及待的小明在超市逛了一圈發現超市里有n件他想要的商品。小明順便對這n件商品打了分，表示商品的實際價值。小明發現身上帶了v1的人民幣，會員卡里面有v2的積分。他想知道他最多能買多大價值的商品。
　　由于小明想要的商品實在太多了，他算了半天頭都疼了也沒算出來，所以請你這位聰明的程序員來幫幫他吧。
Input 輸入包含多組測試用例。
每組數據的第一行是四個整數n，v1，v2，k；
然后是n行，每行三個整數a，b，val，分別表示每個商品的價錢，兌換所需積分，實際價值。
[Technical Specification]
1 <= n <= 100
0 <= v1, v2 <= 100
0 <= k <= 5
0 <= a, b, val <= 100

Ps. 只要錢或者積分滿足購買一件商品的要求，那么就可以買下這件商品。

Output 對于每組數據，輸出能買的最大價值。
詳細信息見Sample。
Sample Input 5 1 6 1 4 3 3 0 3 2 2 3 3 3 3 2 1 0 2 4 2 5 0 0 1 0 4 4 1 3 3 4 3 4 4
Sample Output 12 4 這是一個多維背包問題。狀態轉移方程：dp[v1][v2][k]=MAX(dp[v1-a][v2][k]+c,dp[v1][v2-b][k]+c,dp[v1][v2][k-1]+c)./*dp[j][k][t]表示花j元錢，用了k元積分，免費拿了t件商品以后的最大價值*/ AC代碼：/*dp[j][k][t]表示花j元錢，用了k元積分，免費拿了t件商品以后的最大價值*/ #include<stdio.h> #include<string.h> int dp[102][102][10],a[102],b[102],val[102]; int max(int a,int b) {return a>b?a:b; } int main() {int n,i,v1,v2,j,k,t,p,MAX;while(scanf("%d%d%d%d",&n,&v1,&v2,&p)!=EOF) //n是商品個數，v1是錢數，v2是積分數，p是免費拿的商品數{memset(dp,0,sizeof(dp));for(i=0;i<n;i++)scanf("%d%d%d",&a[i],&b[i],&val[i]); //a[i]是需要多少錢能買這件商品，b[i]是用多少積分能換這件商品，val[i]是這件商品的價值for(i=0;i<n;i++)for(j=v1;j>=0;j--)for(k=v2;k>=0;k--)for(t=p;t>=0;t--){int MAX=0; //不要這件商品則最大價值為0if(j>=a[i]) //能用錢買MAX=max(MAX,dp[j-a[i]][k][t]+val[i]); //用錢買的最大價值if(k>=b[i]) //能用積分兌換MAX=max(MAX,dp[j][k-b[i]][t]+val[i]); //用積分兌換的最大價值if(t>=1) //能免費拿MAX=max(MAX,dp[j][k][t-1]+val[i]); //免費拿的最大價值dp[j][k][t]=max(dp[j][k][t],MAX); // 綜合比較三者以后的最大價值}printf("%d\n",dp[v1][v2][p]); //花v1元且用v2積分兌換且免費拿了k件商品后的最大價值}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4501 小明系列故事——买年货 多重背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。