题目
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 231).
Sample Input
1 5 10 1 2 3 4 5 5 4 3 2 1
Sample Output
14
思考过程
这是一个01背包的模板题。
只要找出状态转移方程就解决了一大半问题。
这个问题我使用了一维数组进行了空间优化，因为题目给的数据的范围是N<=1000;V<=1000。所以需要开一个1000*1000的二位数组,这个数组太大了，超出了题目要求的范围，所以我使用了一个一位数组进行数组滚动。
状态转移方程为：
F[v]=max{ F[v-Ci]+Wi , F[v] }
需要特别注意的一个问题是，由于01背包问题需要比较的是上一个循环中F[v-Ci]+Wi , F[v]的值，因此需要递减循环F[v]
做题期间出现了一个小插曲，我写完之后提交三次，全部WA，全部绿，整的我脸都绿了。仔细检查代码后一点问题也没有，回头看题目才发现自己将题目中的数据顺序看错。。以后我一定要写一篇论文，名字就叫做《论ACM中英语与仔细读英语题目的重要性》。。
AC代码
#include<iostream>#include<stdio.h>#include<string.h>using namespace std;int v[1010];int c[1010];int dp[1010];int MAX(int a, int b){return a > b ? a : b;}int main(){int T, N, V;cin >> T;while (T--){scanf("%d%d", &N, &V);for (int i = 1; i <= N; i++){scanf("%d", &c[i]);}for (int j = 1; j <= N; j++){scanf("%d", &v[j]);}for (int i = 0; i <= 1000; i++){dp[i] = 0;}for (int k = 1; k <= N; k++){for (int l = V; l >=v[k]; l--){dp[l] = MAX(dp[(l - v[k])] + c[k], dp[l]);}}printf("%d ", dp[V]);}}