01背包（Bone Collector）

重新回顾一下背包问题，特来贴一篇博客。

01背包问题

01背包是背包问题的基础，基本上其他背包问题都是由他扩展而来，可以看出他的重要性。

题目：

有N件物品和一个容量为V的背包。放入第i件物品所消耗的空间是C，得到的价值是W_i,求解将那些物品装入背包可以使价值最大。

分析：

对于每一种物品我们只有选与不选两种状态，根据动态规划的一般解题思路，我们首先要确定阶段，状态，决策。

阶段：前i件物品为一个阶段 状态：前i件物品装在容量为j的背包中的最大价值量为一个状态 决策：对每件物品看选取还是不选取那个价值量最大

由此得到动态转移方程：f[i][j] = max(f[i-1][j],f[i-1][j-w[i]] + v[i]);

解释一下这个方程，我们需要的到前i件物品装入容量为j的背包中的最大价值量，只需要知道前i-1件物品装入容量为j的背包中与i-1件物品装入j-w[i]的背包中的最大价值量加上第i件物品的价值量，取一个最大值。为什么可以呢？仔细想想其实他们所代表其实就是第i件物品的选与不选。

给出代码：

for(int i = 1;i <= n; i++) for(int j = w[i];j <= W; j++) f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

这是一个二维的代码，但我们仔细想想会发现，我们求第i件物品时只用到了第i-1件物品所以我们其实可以循环利用这个数组不是吗？下面给出一维代码。

for(int i = 1;i <= N; i++) for(int j = W;j >= w[i]; j--) f[j] = max(f[j],f[j-w[i]]+v[i]);

思考一下为什么要从W到w[i]而不是从w[i]到W。因为之前的i-1件物品的价值量是存在j的前面的，加入我们从前往后dp的话就会在之前修该掉他的值了，而当我们dp到第i位的时候再需要用到i-1的值时便找不到了，所以只能从后往前。

给道题目： 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602

题目：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 231).

Sample Input

1 5 10 1 2 3 4 5 5 4 3 2 1

Sample Output

14

/************************************************************************* > File Name: Bone_Collector.cpp > Author: Frade > Mail: frade@vip.sina.com.cn > Created Time: 2017年05月03日 星期三 11时30分55秒 ************************************************************************/ #include <iostream> #include <cstdio> using namespace std; int Getint() { char c = getchar(); bool flag = false; int ans = 0; while(c != '-' && (c <'0' || c > '9'))c = getchar(); if(c == '-')flag = true,c = getchar(); while(c >= '0' && c <= '9')ans = ans*10 + c - '0',c = getchar(); return (flag == true) ? -ans : ans; } const int maxn = 1000 + 5; int w[maxn],f[maxn],v[maxn]; int main() { int T = Getint(); while(T--) { for(int i = 0;i <= maxn; i++)f[i] = 0,w[i] = 0,v[i] = 0; int N = Getint(); int W = Getint(); for(int i = 1;i <= N; i++)v[i] = Getint(); for(int i = 1;i <= N; i++)w[i] = Getint(); for(int i = 1;i <= N; i++) for(int j = W;j >= w[i]; j--) f[j] = max(f[j],f[j-w[i]]+v[i]); printf("%d\n",f[W]);//空间优化 } return 0; }