从斐波那契到01背包 - 我理解的DP
01背包问题是动态规划的经典入门题目，为了更好的总结与检验，我决定写一篇博文来输出自己的理解。
斐波那契数列的问题早在大一的时候就已经是简单的递归题了，后来大家也发现了直接用数组，从3开始递推就好。
问题就是，递归到底与数组递推有什么关系？
为了搞清楚这个问题，我将Fib的递归函数写下：
int fib (int n) {
if (n == 1 || n == 2) return 1;
return fib(n-1)+fib(n-2);
}
然后设n为5，来模拟fib函数的处理。
fib(5) = fib(4)+fib(3) = [fib(3)+fib(2)] + [fib(2)+fib(1)]
发现，fib(3)这个函数需要执行两次。可以预见，若问题规模变大，将会有大量的重复计算某个fib(i)。所以，正如在许多地方上看到的，我们将每个函数的计算结果保存在数组中。变为记忆化搜索，若有记忆直接使用，否则就计算出来再记下来。
这使得Fib问题最后的处理方式为：
int a[100];
a[1]=a[2]=1;
for(int i = 3; i < 100; i++) a[i] = a[i-1]+a[i-2];
所以忽然想到刚刚问题的答案：
当有重复的子问题需要解决时，我们可以使用数组保存每个子问题的结果来推出父问题的结果，这就是我对DP的理解。
来看01背包问题。
01背包问题
Problem Description
给定n种物品和1个背包，物品i的重量是wi，其价值为vi，背包的容量为C。要求选择装入背包的物品，使得装入背包中物品的总价值最大。
Input
每组测试数据包含3行，第1行为n和c，表示有n(0<=n<=400)个物品且背包容量为c (c<=1500)，第二行为这n个物品的重量wi(1<=wi<=1000)，第三行为这n个物品的价值vi。背包容量和物品重量都为整数。
Output
输出装入背包的最大总价值，每个答案一行。
Sample Input
5 10
2 2 6 5 4
6 3 5 4 6
5 10
3 1 5 9 3
6 6 2 13 2
Sample Output
15
19
原题地址：usx-1006
思考这个问题，都会发现其实是求在总重量小于c的约束条件下，对n件物品装与不装的合法组合的最优解。
再考虑如果将第1件物品(重量w，价值v)装入，那么问题结果就成为了总重量小于c-w的约束条件下，对n-1件物品装与不装的合法组合的最优解，再加上v。
忽然发现存在子问题，那么不妨我们将每个问题的结果都保存在数组dp中。
设dp[i]为对前i件物品的最优解。
那么对于每件物品j（Wj<c），都有以下关系：
dp[i] = max(dp[i]， dp[i - w[j] + v[j]);
即前i件物品的最优解就是不将j装进去，与将j装进去这两种解决方案的最优解。
循环询问每件物品装或不装进去的最优解就可以了。
最终解法见下方代码。
Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn = 410;
const int maxc = 1510;
using namespace std;
int dp[maxc], w[maxn], v[maxn];
int n, c;
int main () {
while(scanf("%d%d", &n, &c) != EOF) {
for(int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
for(int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) { // 用每件物品询问装还是不装
for(int j = c; j >= w[i]; j--) { // 在物品能装进去的容量下，求该容量下最优解
// 容量为j时，放前n个物品最大价值
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
printf("%d", dp[c]);
}
return 0;
}
