從斐波那契到01背包 - 我理解的DP

01背包問題是動態(tài)規(guī)劃的經(jīng)典入門題目，為了更好的總結(jié)與檢驗(yàn)，我決定寫一篇博文來輸出自己的理解。

斐波那契數(shù)列的問題早在大一的時(shí)候就已經(jīng)是簡單的遞歸題了，后來大家也發(fā)現(xiàn)了直接用數(shù)組，從3開始遞推就好。

問題就是，遞歸到底與數(shù)組遞推有什么關(guān)系？

為了搞清楚這個(gè)問題，我將Fib的遞歸函數(shù)寫下：

int fib (int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n-1)+fib(n-2);
}

然后設(shè)n為5，來模擬fib函數(shù)的處理。

? fib(5) = fib(4)+fib(3) = [fib(3)+fib(2)] + [fib(2)+fib(1)]

發(fā)現(xiàn)，fib(3)這個(gè)函數(shù)需要執(zhí)行兩次。可以預(yù)見，若問題規(guī)模變大，將會有大量的重復(fù)計(jì)算某個(gè)fib(i)。所以，正如在許多地方上看到的，我們將每個(gè)函數(shù)的計(jì)算結(jié)果保存在數(shù)組中。變?yōu)橛洃浕阉?，若有記憶直接使用，否則就計(jì)算出來再記下來。

這使得Fib問題最后的處理方式為：

int a[100];
a[1]=a[2]=1;
for(int i = 3; i < 100; i++) a[i] = a[i-1]+a[i-2];

所以忽然想到剛剛問題的答案：

當(dāng)有重復(fù)的子問題需要解決時(shí)，我們可以使用數(shù)組保存每個(gè)子問題的結(jié)果來推出父問題的結(jié)果，這就是我對DP的理解。

來看01背包問題。

01背包問題

Problem Description

給定n種物品和1個(gè)背包，物品i的重量是wi，其價(jià)值為vi，背包的容量為C。要求選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。

Input

每組測試數(shù)據(jù)包含3行，第1行為n和c，表示有n(0<=n<=400)個(gè)物品且背包容量為c (c<=1500)，第二行為這n個(gè)物品的重量wi(1<=wi<=1000)，第三行為這n個(gè)物品的價(jià)值vi。背包容量和物品重量都為整數(shù)。

Output

輸出裝入背包的最大總價(jià)值，每個(gè)答案一行。

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

思考這個(gè)問題，都會發(fā)現(xiàn)其實(shí)是求在總重量小于c的約束條件下，對n件物品裝與不裝的合法組合的最優(yōu)解。

再考慮如果將第1件物品(重量w，價(jià)值v)裝入，那么問題結(jié)果就成為了總重量小于c-w的約束條件下，對n-1件物品裝與不裝的合法組合的最優(yōu)解，再加上v。

忽然發(fā)現(xiàn)存在子問題，那么不妨我們將每個(gè)問題的結(jié)果都保存在數(shù)組dp中。

設(shè)dp[i]為對前i件物品的最優(yōu)解。

那么對于每件物品j（Wj<c），都有以下關(guān)系：

dp[i] = max(dp[i]， dp[i - w[j] + v[j]);

即前i件物品的最優(yōu)解就是不將j裝進(jìn)去，與將j裝進(jìn)去這兩種解決方案的最優(yōu)解。

循環(huán)詢問每件物品裝或不裝進(jìn)去的最優(yōu)解就可以了。

最終解法見下方代碼。

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)去的容量下，求該容量下最優(yōu)解
                // 容量為j時(shí)，放前n個(gè)物品最大價(jià)值
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            }
        }

        printf("%d", dp[c]);
    }

    return 0;
}