本文主要是介绍hdu 4501 (多维背包)小明系列故事——买年货，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这么多维的背包，第一次写。
刚开始，一直以一维背包的思维在写。一直wa。
后来，看了下网上的。一对照，发现，并不是对于小于w[i]的就不计算了。而是要计算到0，因为当一个状态不满足时，另两个状态可能满足，也是要计算的。
#include <iostream>
using namespace std;int max(int a,int b)
{return a>b?a:b;
}int main()
{
// freopen("in.txt","r",stdin);int n,v1,v2,k;int a[110],b[110],val[110],dp[110][110][10];while(scanf("%d %d %d %d",&n,&v1,&v2,&k)==4){for(int i=0;i<n;i++)scanf("%d %d %d",&a[i],&b[i],&val[i]);for(int i=0;i<=v1;i++)for(int j=0;j<=v2;j++)for(int x=0;x<=k;x++)dp[i][j][x]=0;for(int i=0;i<n;i++){if(val[i])for(int x=v1;x>=0;x--)for(int y=v2;y>=0;y--)for(int z=k;z>=0;z--){int tmp=0;if(x-a[i]>=0)tmp=max(tmp,dp[x-a[i]][y][z]+val[i]);if(y-b[i]>=0)tmp=max(tmp,dp[x][y-b[i]][z]+val[i]);if(z-1>=0)tmp=max(tmp,dp[x][y][z-1]+val[i]);dp[x][y][z]=max(tmp,dp[x][y][z]);}}printf("%d\n",dp[v1][v2][k]);}return 0;
}
这篇关于hdu 4501 (多维背包)小明系列故事——买年货的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
