hdu 4501 小明系列故事——买年货（多维费用01背包） dp

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4501
题意：买东西，钱有v1，积分有v2，可以免费拿k件，相当于三种方式的费用，买一件东西只需使用一种方式的费用就行了
才开始接触dp，纠结好几天终于懂了。
因为是01背包，所以从后往前循环，但是因为是多维的，如果还像普通01背包那样写成for(i=v; i>=cost[j]; i--)就会有问题，因为可能当前这重循环就不满足要求，那么就不会执行更内部的循环，多重循环有自己的优先级，但是这个题里买一件东西三种方式的优先级是相等的，所以就不能直接在循环里限制循环条件，要在循环体里判断才行。

#include #include #define max(a,b) (a)>(b)?(a):(b) int dp[10][105][105]; //免费、钱、积分 int n,v1,v2,t; //钱、积分、商品数量 int costa[105],costb[105],val[105]; //钱,积分,价值 int main() { int i,j,k,p; while(scanf("%d%d%d%d",&n,&v1,&v2,&t)!=EOF) { for(i=0; i=0; i--) for(j=v1; j>=0; j--) for(k=v2; k>=0; k--) { int temp=0; if(i>=1) temp=max(temp,dp[i-1][j][k]+val[p]); if(j>=costa[p]) temp=max(temp,dp[i][j-costa[p]][k]+val[p]); if(k>=costb[p]) temp=max(temp,dp[i][j][k-costb[p]]+val[p]); dp[i][j][k]=max(temp,dp[i][j][k]); } printf("%d\n",dp[t][v1][v2]); } return 0; }

【hdu 4501 小明系列故事——买年货（多维费用01背包）】