有n個重量和價值分別為wi，vi的物品。從這些物體中挑選出總重量不超過W的物品，求所有方案中價值總和的最大值。

1 樸素方法

** 將每個物體是否放入背包進行搜索試一試 **

int n, W;
int w[MAX_N], v[MAX_N];

//從第i個物品選擇總重小于j的部分
int res(int i, int j) {
    int res;
    if (i == n) {
        //已經(jīng)沒有剩余物品了
        res = 0;
    } else if (j < w[i]) {
        //無法挑選這個物品
        res = rec(i + 1, j);
    } else {
        //挑選和不挑選的情況都試一下，不選這個選下一個或許v更大
        res = max(rec(i + 1, j), rec(i + 1, j + 1) + v[i]);
    }
    return res;
}

void solve() {
    printf("%d\n", rec(0, W));
}

** 這種方法的搜索深度是n，每一層需要兩次分支，最壞需要O($2^n$)的時間。**

2 使用數(shù)組記錄結(jié)果，省略第二次以后的重復計算時間。

int dp[MAX_N + 1][MAX_N + 1]; //記憶化數(shù)組

int rec(int i, int j) {
    if (dp[i][j] >= 0) {
        //已經(jīng)計算過的話直接使用之前的結(jié)果
        return dp[i][j];
    }
    int res;
    if (i == n) {
        res = 0;
    } else if (j <w[j]) {
        res = rec(i + 1, k);
    } else {
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
    }
    //將結(jié)果記入dp數(shù)組
    return dp[i][j] = res;
}

void solve() {
    //用-1表示尚未計算過，初始化整個數(shù)組
    memset(dp, -1, sizeof(dp));
    printf("%d\n", rec(0, w));
}

** 根據(jù)定義，有如下的遞推式 **
dp[n][j] = 0;
dp[i][j] = dp[i + 1][j] (j < w[i])
else = max(dp[i + 1][j], dp[i + 1][j -w[i]]+v[i])

int dp[MAX_N + 1][MAX_N + 1]; //記憶化數(shù)組

void solve() {
    for (int i = n - 1; i >= 0; i --) {
        for (int j = 0; i < j<= W; ++j) {
            if (j < w[i]) {
                dp[i][j] = dp[i + 1][j];
            } else {
                dp [i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
        
    }
    printf("%d\n", dp[0][W]);
}

** 上面所述的dp中i的循環(huán)是逆向進行的，如果按照下面定義遞推，則可以正向進行i的循環(huán) **
dp[i + 1][j] :=從0到i這i+1個物品中選出來總重量不超過j的物品時總價值的最大值
dp [0][j] = 0;

dp[i + 1][j] = dp [i][j] (j < w[i])
else = max(dp[i][j], dp[i][j - w[i]] + v[i])

void solve() {
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if (j < w[i]) 
            {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            }
        }
    }
    printf("%d\n", dp[n][w]);
}

** 還可以把狀態(tài)轉(zhuǎn)移想象成從"前i個物品中選取總重不超過j時的狀態(tài)"向"前i + 1個物品中選取總重不超過j"和"前i+1個物品中選取總重不超過j+w[i]時的狀態(tài)"的轉(zhuǎn)移，于是可以實現(xiàn)下面形式 **

void solve() {
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            dp[i + 1][j] = max(dp[i+1][j], dp[i][j]);
            if (j + w[i] <= W) 
            {
                dp[i + 1]{j + w[i] = max(dp[i + 1][j + w[i], dp[i][j] + v [i]); 
            }
        }
    }
    printf("%d\n", dp[n][w]);
}