Bone Collector
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<iostream>
#include<cstring>
#include<cstdio>
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<iostream>
#include<cstring>
#include<cstdio>
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;
}