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 ?
1 5 10 1 2 3 4 5 5 4 3 2 1
14
1 /************************************************************************* 2 > File Name: 0-1.cpp 3 > Author: Mercu 4 > Mail: bkackback1993@gmail.com 5 > Created Time: 2014年07月20日 星期日 09时17分15秒 6 ************************************************************************/ 7 8 #include<iostream> 9 #include<string.h> 10 using namespace std; 11 12 int t[1005],v[1005]; 13 int f[1005]; 14 int ozzy(int a,int b) 15 { 16 17 } 18 int main() 19 { 20 int o,a,i,b,c; 21 int maxv; 22 cin>>o; 23 while(o--) 24 { 25 int j,k,l; 26 cin>>a>>b; 27 memset(v,0,sizeof(v)); 28 memset(t,0,sizeof(t)); 29 memset(f,0,sizeof(f)); 30 for(i = 1;i <= a;i++) 31 { 32 cin>>v[i]; 33 } 34 for(i = 1;i <= a;i++) 35 { 36 cin>>t[i]; 37 } 38 39 for(i = 1;i <= a;i++) 40 { 41 for(j = b;j >= t[i];j--) 42 { 43 if(t[i] <= j) 44 f[j] = max(f[j],f[j - t[i]] + v[i]); 45 } 46 } 47 cout<<f[b]<<endl; 48 } 49 return 0; 50 }
这个题是一个很明显的0-1背包问题,就是给定的物品,有两种状态,一种是放,一种是不放,一个物品不能放多次.
1 for(i = 1;i <= a;i++) 2 { 3 for(j = b;j >= t[i];j--) 4 { 5 if(t[i] <= j) 6 f[j] = max(f[j],f[j - t[i]] + v[i]); 7 } 8 }
这一段是核心代码,要注意for的范围,第一个for从1到a,a是什么?a是物品的个数,第二个for从b到t[i] t[i]是物品的体积.b是最大体积,所以
1 for 1 -->n // 1/0取决于输入w[i] v[i]的时候下标0开始还是1开始 2 for b -->w[i] 3 if(w[i] <= b) 4 f[j] = max(f[j],f[j-t[i]] + v[i]]);
其中,w[i]是质量,v[i]是价值(质量和价值 == 体积和价值).
JXUST第二赛-B. Bone Collector,布布扣,bubuko.com
原文：http://www.cnblogs.com/mercu/p/3857949.html