可以看成是3维背包问题,开的是四维数组,这个地方最好是用四维数组,因为有花费为0但是却又价值(估计现实是不会有的)的物品。
f[i][j][k][t] 是 在前 i 件物品中,最多花费 金钱 j,积分 k,消费券 k 的时候最大能够 获得的价值
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define CLR(arr,val) memset(arr,val,sizeof(arr)); #define max(a,b) a > b ? a : b int dp[101][101][101][6]; int main() { //freopen("in.txt","r",stdin); int n,V1,V2,free; while(~scanf("%d%d%d%d",&n,&V1,&V2,&free)) { CLR(dp[0],0); for(int i = 1 ; i <= n;i++ ) { int c1,c2,v; scanf("%d%d%d",&c1,&c2,&v); for(int j = 0 ;j <= V1 ;j++) //都是从0开始的,避免数组的前面几个元素断层,就是无法执行不选物品i的情况,更重要的情况是可能用积分或者免费拿(即使用钱买不起) { for(int k = 0;k <= V2 ; k++) { for(int t = 0;t <= free;t++) { dp[i][j][k][t] = dp[i-1][j][k][t]; //不选用第 i 件物品 if(t >= 1 ) dp[i][j][k][t] = max(dp[i][j][k][t],dp[i-1][j][k][t - 1] + v); // 用消费券 if(k - c2 >= 0) dp[i][j][k][t] = max(dp[i][j][k][t],dp[i-1][j][k - c2][t] + v ); // 用积分 if(j - c1 >= 0) dp[i][j][k][t] = max(dp[i][j][k][t],dp[i-1][j - c1][k][t] + v); //用钱 } } } } printf("%d\n",dp[n][V1][V2][free]); } return 0; }