hdu 4501 小明系列故事——买年货_二维双肩包
hdu 4501 小明系列故事——买年货_二维背包
题目:你可以有v1元,v2代金券,v3个物品免单,现在有n个商品,商品能用纸币或者代金券购买,当然你可以买v3个商品免费。问怎么最大能买多少价值
题意:
思路二维背包,dp[v1][v2][v3]=MAX(dp[v1-n.a][v2][v3]+n.value,dp[v1][v2-n.b][v3]+n.value,dp[v1][v2][v3-1]+n.value)
#include <iostream> #include<cstdio> #include<cstring> using namespace std; int dp[110][110][6]; struct node{ int value; int a; int b; }bla[110]; int main(int argc, char** argv) { int n,v1,v2,v3,i,j,k,x,y,tmp; while(scanf("%d%d%d%d",&n,&v1,&v2,&v3)!=EOF){ memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) scanf("%d%d%d",&bla[i].a,&bla[i].b,&bla[i].value); for(i=0;i<n;i++) for(j=v1;j>=0;j--) for(k=v2;k>=0;k--) for(x=v3;x>=0;x--){ tmp=0; if(j>=bla[i].a) tmp=max(tmp,dp[j-bla[i].a][k][x]+bla[i].value); if(k>=bla[i].b) tmp=max(tmp,dp[j][k-bla[i].b][x]+bla[i].value); if(x>0) tmp=max(tmp,dp[j][k][x-1]+bla[i].value); dp[j][k][x]=max(tmp,dp[j][k][x]); } printf("%d\n",dp[v1][v2][v3]); } return 0; }