http://acm.hdu.edu.cn/showproblem.php?pid=4501
可以看作三维背包问题。
但是我犯了个错误。
错误原因是物品的的价格或者兑换所需积分可能为0；
用0-1背包v[n*v]减少空间的方法的思想时：当处理价格或者兑换所需积分为0的商品时,会导致重复处理（重复放入）物品。
例如：
if(j>=c1[i])
dp[j][k][g]=Max(dp[j][k][g],dp[j-c1[i]][k][g]+v[i]);
if(k>=c2[i])
dp[j][k][g]=Max(dp[j][k][g],dp[j][k-c2[i]][g]+v[i]);
当c1[i]=c2[i]=0时，dp[j][k][g]加了2次。
if(j>=c1[i])
dp[flag][j][k][g]=Max(dp[flag][j][k][g],dp[flag^1][j-c1[i]][k][g]+v[i]);
if(k>=c2[i])
dp[flag][j][k][g]=Max(dp[flag][j][k][g],dp[flag^1][j][k-c2[i]][g]+v[i]);
而用四位的数组则保护了原数据。
正确代码
#include<iostream>
#include<cstring>
using namespace std;
int Max(int a,int b)
{
if(a>b)
return a;
return b;
}
int main()
{
int c1[103],c2[103],v[103],k,dp[2][103][103][6],n,v1,v2,f,j,t,g,flag;
while(cin>>n!=0)
{
flag=0;
memset(dp,0,sizeof(dp));
cin>>v1>>v2>>f;
for(int i=1;i<=n;i++)
cin>>c1[i]>>c2[i]>>v[i];
for(i=1;i<=n;i++)
{
flag^=1;
for(j=v1;j>=0;j--)
for(k=v2;k>=0;k--)
for(g=f;g>=0;g--)
{
dp[flag][j][k][g]=dp[flag^1][j][k][g];
if(j>=c1[i])
dp[flag][j][k][g]=Max(dp[flag][j][k][g],dp[flag^1][j-c1[i]][k][g]+v[i]);
if(k>=c2[i])
dp[flag][j][k][g]=Max(dp[flag][j][k][g],dp[flag^1][j][k-c2[i]][g]+v[i]);
if(g>=1)
dp[flag][j][k][g]=Max(dp[flag][j][k][g],dp[flag^1][j][k][g-1]+v[i]);
}
}
cout<<dp[flag][v1][v2][f]<<endl;
}
return 0;
}
错误代码
#include<iostream> #include<cstring> using namespace std; int Max(int a,int b) { if(a>b) return a; return b; } int main() { int c1[103],c2[103],v[103],k,dp[103][103][6],n,v1,v2,f,j,t,g; while(cin>>n!=0) { memset(dp,0,sizeof(dp)); cin>>v1>>v2>>f; for(int i=1;i<=n;i++) cin>>c1[i]>>c2[i]>>v[i]; for(i=1;i<=n;i++) for(j=v1;j>=0;j--) for(k=v2;k>=0;k--) for(g=f;g>=0;g--) { if(j>=c1[i]) dp[j][k][g]=Max(dp[j][k][g],dp[j-c1[i]][k][g]+v[i]); if(k>=c2[i]) dp[j][k][g]=Max(dp[j][k][g],dp[j][k-c2[i]][g]+v[i]); if(g>=1) dp[j][k][g]=Max(dp[j][k][g],dp[j][k][g-1]+v[i]); } for(j=v1;j>=0;j--) for(k=v2;k>=0;k--) for(g=f;g>=0;g--) cout<<j<<" "<<k<<" "<<g<<" "<<dp[j][k][g]<<endl; } return 0; }