本文主要是介绍hdu2159 二维完全背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题http://acm.hdu.edu.cn/showproblem.php?pid=2159
第一次遇到多维的背包，其实只是多种因素同时限制最终背包值。
比如这一题，二维，加一重循环并找准上一层的状态就行了。代码一看就能会。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define max(a,b)(a>b?a:b)
int c[105]; //
int w[105];
int f[105][105];
int n,m,k,s; //经验值 忍耐度 种类 杀怪数
int main()
{
// freopen("C:\\1.txt","r",stdin);
while(~scanf("%d%d%d%d",&n,&m,&k,&s))
{
memset(f,0,sizeof(f));
int i,j,l;
for(i=1;i<=k;i++)
scanf("%d%d",&w[i],&c[i]); //经验值 忍耐度
for(i=1;i<=k;i++)
{
for(j=1;j<=s;j++) //杀怪数
{
for(l=c[i];l<=m;l++) //忍耐度
{
f[j][l]=max(f[j][l],f[j-1][l-c[i]]+w[i]);
}
}
}
int ans=-1;
for(j=0;j<=s;j++)
for(l=0;l<=m;l++)
if(f[j][l]>=n&&ans<m-l)
ans=m-l;
printf("%d\n",ans);
}
return 0;
}
这篇关于hdu2159 二维完全背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
