本文共 2375 字，大约阅读时间需要 7 分钟。

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 ? 

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.

Output

One integer per line representing the maximum of the total value (this number will be less than 2 31).

Sample Input

1

5 10

1 2 3 4 5

5 4 3 2 1

Sample Output 

14

题意：

有n种骨头和一个袋子，每种骨头都有他自己的体积和价值，用袋子去装骨头，求出袋子所能装下的骨头的最大的价值。

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int maxn = 1005;const int inf=0x3f3f3f3f;int dp[maxn][maxn];int v[maxn],w[maxn];int main(){	int n,vv,t;	memset(dp,0,sizeof(dp));	scanf("%d",&t);	while(t--)	{		scanf("%d%d",&n,&vv);   //骨头种类和袋子的体积 		for(int i=1;i<=n;i++)		{			scanf("%d",&v[i]);   //各个骨头的价值 		}		for(int i=1;i<=n;i++)		{			scanf("%d",&w[i]);   //各个骨头的体积 		}  		for(int i=1;i<=n;i++)		{			for(int j=vv;j>=w[i];j--)			 dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);		 		}         printf("%d\n",dp[n][vv]);	}	return 0;}
     
    
   

附加：显示出袋子中装了哪些物品

#include
   
    #include
    
     #include
     
      using namespace std;const int maxn = 1005;const int inf=0x3f3f3f3f;int dp[maxn][maxn];int v[maxn],w[maxn];int main(){	int n,vv,t;	memset(dp,0,sizeof(dp));	scanf("%d",&t);	while(t--)	{		scanf("%d%d",&n,&vv);   //骨头种类和袋子的体积 		for(int i=1;i<=n;i++)		{			scanf("%d",&v[i]);   //各个骨头的价值 		}		for(int i=1;i<=n;i++)		{			scanf("%d",&w[i]);   //各个骨头的体积 		}  		for(int i=1;i<=n;i++)		{			for(int j=vv;j>=w[i];j--)			 dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]); 		}		printf("背包中装的各个骨头的价值：\n");		int j=vv,i=n;		while(i>=1&&j>=0)		{			if(dp[i][j]==dp[i-1][j-w[i]]+v[i])			{				printf("%d\n",i);				j-=w[i];			}			i--; 		}				}	return 0;}
     
    
   

转载地址：http://fszci.baihongyu.com/