小明系列故事——買年貨

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[i][j][k]表示現金，積分卡，免費拿物品的個數分別為i，j，k時可以獲得的最大價值。剩下的就是類似于01背包了。 不過這里要注意當a和b當中存在0的時候要注意，這里坑了我好久。 #include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 105; struct Node {int a,b,val; }goods[maxn]; int n,v1,v2,m,k,dp[maxn][maxn][10];int main() {while(scanf("%d%d%d%d",&n,&v1,&v2,&m)!=EOF){for(int i = 1; i <= n; i++)scanf("%d%d%d",&goods[i].a,&goods[i].b,&goods[i].val);memset(dp,0,sizeof(dp));for(int i = 1; i <= n; i++)for(int j = v1; j >= 0; j--)for(int k = v2; k >= 0; k--)for(int t = m; t >= 0; t--){if(goods[i].a == 0 || goods[i].b == 0) //這里不能是&&，假如a！=0，b=0，那么dp[j][k][t]可能會算重。dp[j][k][t] += goods[i].val;else{if(j >= goods[i].a)dp[j][k][t] = max(dp[j][k][t],dp[j-goods[i].a][k][t] + goods[i].val);if(k >= goods[i].b)dp[j][k][t] = max(dp[j][k][t],dp[j][k-goods[i].b][t] + goods[i].val);}if(t >= 1)dp[j][k][t] = max(dp[j][k][t],dp[j][k][t-1] + goods[i].val);}int ans = 0;for(int i = 0; i <= v1; i++)for(int j = 0; j <= v2; j++)for(int k = 0; k <= m; k++)ans = max(ans,dp[i][j][k]);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4501(三维背包问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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