Descriptions: 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
题目链接： https://vjudge.net/problem/HDU-2602
题解：
先说翻译（翻译计较简化，不影响做题） 已知N个糖果的重量和价值. 我们有一个口袋, 最多可以装V重量的糖果. 问口袋最多能放多少价值的糖果进去? 输入 第一行是T, 表示有T组数据. 每组数据由三行组成. 第一行包含两个整数N和V(N <= 1000, V <= 1000). N表示糖果的个数, V表示口袋的载重. 第二行包含N个整数, 表示每一颗糖果的价值. 第三行包含N个整数, 表示每一颗糖果的重量. 输出 对每一组数据, 输出口袋最终可以放进去糖果的价值 题解开始： 标准的01背包问题，非常经典，就是变成了多组测试，没什么太大影响，照样dp。用数组记录每一件物品的重量w[i]，价值v[i]，背包各个重量的最优解dp[j]，从第一个物品到最后一个物品，背包空间初始为M（题目给定的值），放入第i件物品，空间减少w[i]，价值增加v[i]，不断更新直到背包空间为0。 状态更新公式：dp[j]=max(dp[j],dp[j-w[i]]+v[i]
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> using namespace std; int v[13000];//价值 int w[13000];//重量 int dp[13000]; int main() { int N,V; int T; cin >> T; while(T--) { memset(dp,0,sizeof(dp));//多组输入，所以每次都要更新数组 memset(v,0,sizeof(v)); memset(w,0,sizeof(w)); cin >> N >>V; for(int i=0; i<N; i++)//从第0到第N-1件物品 cin >> v[i]; for(int i=0; i<N; i++) cin >> w[i]; for(int i=0; i<N; i++) { for(int j=V; j>=w[i]; j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//dp更新中，保证j-w[i]必须大于0，即背包空间一直大于0 } } cout << dp[V] << endl; } return 0; }