题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602
Bone Collector
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 54132 Accepted Submission(s):
22670
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 …
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 ?
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 …
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 ?
Input
The first line contain a integer T , the number of
cases.
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.
cases.
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 231).
total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
01背包问题，这种背包特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即dp[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：
dp[i][v]=max{dp[i-1][v],dp[i-1][v-cost[i]]+value[i]}
用子问题定义状态：即dp[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：
dp[i][v]=max{dp[i-1][v],dp[i-1][v-cost[i]]+value[i]}
#include<iostream>
using namespace std;
int dp[][]; int max(int x,int y)
{
return x>y?x:y;
} int main()
{
int t,n,v,i,j;
int va[],vo[];
cin>>t;
while(t--)
{
cin>>n>>v;
for(i=;i<=n;i++)
cin>>va[i];
for(i=;i<=n;i++)
cin>>vo[i];
memset(dp,,sizeof(dp));//初始化操作
for(i=;i<=n;i++)
{
for(j=;j<=v;j++)
{
if(vo[i]<=j)//表示第i个物品将放入大小为j的背包中
dp[i][j]=max(dp[i-][j],dp[i-][j-vo[i]]+va[i]);//第i个物品放入后，那么前i-1个物品可能会放入也可能因为剩余空间不够无法放入
else //第i个物品无法放入
dp[i][j]=dp[i-][j];
}
}
cout<<dp[n][v]<<endl;
}
return ;
}
该题的第二种解法就是对背包的优化解法，当然只能对空间就行优化，时间是不能优化的。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组dp[i][0..V]的所有值。
那么，如果只用一个数组dp[0..V]，能不能保证第i次循环结束后dp[v]中表示的就是我们定义的状态dp[i][v]呢？
dp[i][v]是由dp[i-1][v]和dp[i-1][v-c[i]]两个子问题递推而来，能否保证在推dp[i][v]时（也即在第i次主循环中推dp[v]时）能够得到dp[i-1][v]和dp[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推dp[v]，这样才能保证推dp[v]时dp[v-c[i]]保存的是状态dp[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
dp[v]=max{dp[v],dp[v-c[i]]+w[i]};
注意：这种解法只能由V--0，不能反过来，如果反过来就会造成物品重复放置！
#include<iostream>
using namespace std;
#define Size 1111
int va[Size],vo[Size];
int dp[Size];
int Max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int t,n,v;
int i,j;
cin>>t;
while(t--)
{
cin>>n>>v;
for(i=;i<=n;i++)
cin>>va[i];
for(i=;i<=n;i++)
cin>>vo[i];
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
for(j=v;j>=vo[i];j--)
{
dp[j]=Max(dp[j],dp[j-vo[i]]+va[i]);
}
}
cout<<dp[v]<<endl;
}
return ;
}