http://acm.hdu.edu.cn/showproblem.php?pid=2602简单的0、1背包问题
//二维数组实现01背包
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][1001],vol[1001],val[1001];
int main()
{
int t,n,i,j,v;
cin>>t;
while(t--)
{
cin>>n>>v;
for(i=1;i<=n;i++)
scanf("%d",&val[i]);
for(i=1;i<=n;i++)
scanf("%d",&vol[i]);
memset(dp,0,sizeof(dp)); //初始化
/**//*
//dp[i][j]，i表示体积,j表示个数也没问题，以后就不用担心内外循环写错的问题了
for(i=0;i<=v;i++) //从0开始
for(j=1;j<=n;j++)
if(vol[j]<=i && dp[i][j-1]<dp[i-vol[j]][j-1]+val[j])
dp[i][j]=dp[i-vol[j]][j-1]+val[j];
else
dp[i][j]=dp[i][j-1];
*/
for(i=1;i<=n;i++)
for(j=0;j<=v;j++) //注意要从0开始，这个题测试数据有点变态，有的骨头有价值，但占的空间是0
{
if(vol[i]<=j && dp[i-1][j]<dp[i-1][j-vol[i]]+val[i])
dp[i][j]=dp[i-1][j-vol[i]]+val[i];
else
dp[i][j]=dp[i-1][j];
}
//cout<<dp[v][n]<<endl;
cout<<dp[n][v]<<endl;
}
return 0;
}
该题有组测试数据变态，如下：
1
2 0
20 1
0 1
答案是： 20
//一维数组实现01背包
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001],vol[1001],val[1001];
int main()
{
int t,n,i,j,v;
cin>>t;
while(t--)
{
cin>>n>>v;
for(i=1;i<=n;i++)
scanf("%d",&val[i]);
for(i=1;i<=n;i++)
scanf("%d",&vol[i]);
memset(dp,0,sizeof(dp)); //初始化
for(i=1;i<=n;i++)
for(j=v;j>=vol[i];j--)
if(dp[j]<dp[j-vol[i]]+val[i])
dp[j]=dp[j-vol[i]]+val[i];
cout<<dp[v]<<endl;
}
return 0;
}
posted on 2011-04-07 15:17
大大木马 阅读(3550)
评论(0) 编辑 收藏 引用