Bone CollectorTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 52370Accepted Submission(s): 22079Pr
Bone Collector
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)@H_301_7@
Total Submission(s): 52370 Accepted Submission(s): 22079@H_301_7@
Problem Description
Many years ago,in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones,such as dog’s,cow’s,also he went to the grave …@H_301_7@
The bone collector had a big bag with a volume of V,and along his trip of collecting there are a lot of bones,obvIoUsly,different bone has different value and different volume,now given the each bone’s value along his trip,can you calculate out the
maximum of the total value the bone collector can get ?@H_301_7@
@H_301_7@
Input
The first line contain a integer T,the number of cases.@H_301_7@
Followed by T cases,each case three lines,the first line contain two integer N,V,(N <= 1000,V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third
line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 2@H_301_40@31).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
Author
Teddy
Source
HDU 1st “Vegetable-Birds Cup” Programming
Open Contest
Recommend
lcy
原题链接：http://acm.split.hdu.edu.cn/showproblem.PHP?pid=2602
01背包入门题：
转态转移方程：
f[i][v] = max ( f[i⑴][v],f[i⑴][v-c[i] ]+w[i] )
f[i][v]:前 i 件物品放入容量为v的背包取得最大价值。
c[i]: 第 i 件物品的体积。
w[i] :第 i 件物品的体积价值。
注意：输入数据的时候数组下标要从 1 开！
@H_301_7@
优化成1维的：
伪代码：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
@H_301_7@
f[v] : 体积为v的背包的最大价值。
@H_301_7@
参考博客：http://www.wutianqi.com/?p=539
http://www.cnblogs.com/jiangjun/archive/2012/05/08/2489590.html@H_301_7@
2维AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
int v[maxn];
int val[maxn];
int dp[maxn][maxn];
int main()
{
int T,n,V;
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("data/2602.txt","r",stdin);
cin>>T;
while(T--)
{
cin>>n>>V;
memset(dp,sizeof(dp));
//memset(v,sizeof(v));
//memset(val,sizeof(val));
for(int i=1;i<=n;i++)
cin>>val[i];
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=V;j++)
{
if(j>=v[i])
dp[i][j]=max(dp[i⑴][j],dp[i⑴][j-v[i]]+val[i]);
else
dp[i][j]=dp[i⑴][j];
}
}
cout<<dp[n][V]<<endl;
}
return 0;
}
@H_301_7@
@H_301_7@
优化成1维AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,v[1005],val[1005],dp[1005];
scanf("%d%d",&n,&V);
int i,j,k;
for(i=0; i<n; i++)
scanf("%d",&val[i]);
for(i=0; i<n; i++)
scanf("%d",&v[i]);
memset(dp,sizeof(dp));
for(i=0; i<n; i++)
for(j=V; j>=v[i]; j--)
dp[j]=max(dp[j],dp[j-v[i]]+val[i]);
printf("%d\n",dp[V]);
}
return 0;
}
@H_301_7@
@H_301_7@
尊重原创，转载请注明出处：http://blog.csdn.net/hurmishine@H_301_7@
@H_301_7@
@H_301_7@
@H_301_7@
@H_301_7@
服务热线 19970861797
