3维动态规划 hdu 4501 小明系列故事——买年货
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4501
题目大意：
一共有n件商品，每件商品有一个购买价钱，购买积分，得分价值。
现有k件物品的选购机会，有v1元钱，v2积分，问能获得的最大得分价值是多少。
解题思路：
dp[i][j][k]表示有i元钱，j积分和k个免费商品的机会，能获得的最大的得分价值。
对每件商品一共有四种选择，1、用钱买 2、用积分换 3、用一个免费商品的名额 4、什么都不用
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;int dp[110][110][10]; //dp[i][j][k]表示有i人民币，j积分,k次免费的机会能够获得的最大价值struct Thing{ int a,b,val;}thing[110];int main(){ int n,v1,v2,k; while(scanf("%d%d%d%d",&n,&v1,&v2,&k)!=EOF) { int sum=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&thing[i].a,&thing[i].b,&thing[i].val); sum+=thing[i].val; } memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int q=k;q>=0;q--) for(int j=v1;j>=0;j--) for(int p=v2;p>=0;p--) { if(j>=thing[i].a&&p>=thing[i].b) //如果能够用积分或钱 { dp[j][p][q]=max(max(dp[j-thing[i].a][p][q]+thing[i].val,dp[j][p-thing[i].b][q]+thing[i].val),dp[j][p][q]); if(q>=1) //如果能用免费的名额 dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val); } else if(j<thing[i].a&&p<thing[i].b) //如果钱和积分都不能用 { if(q>=1) dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val); } else if(j<thing[i].a) //只能用积分 { dp[j][p][q]=max(dp[j][p-thing[i].b][q]+thing[i].val,dp[j][p][q]); if(q>=1) dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val); } else //只能用钱 { dp[j][p][q]=max(dp[j-thing[i].a][p][q]+thing[i].val,dp[j][p][q]); if(q>=1) dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val); } } printf("%d\n",dp[v1][v2][k]); } return 0;}