01背包問題

有 N 件物品和一個容量是 V 的背包。每件物品隻能使用一次。

第 i 件物品的體積是 vi，價值是 wi。

求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。

輸出最大價值。

輸入格式

第一行兩個整數，N，V，用空格隔開，分别表示物品數量和背包容積。

接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分别表示第 i 件物品的體積和價值。

輸出格式

輸出一個整數，表示最大價值。

資料範圍

0 < N, V <= 1000

0 < vi, wi <= 1000

Example 1:

Input:

4 5

1 2

2 4

3 4

4 5

Output:

8

題解思路 DP

我們定義

fi 表示從前i個物品中，選擇總體積不超過j的所有物品集合的最大價值

那麼

1.當我們不選擇物品i時,

f[i][j] = f[i - 1][j]

2.當我們選擇物品i時

f[i][j] = f[i - 1][j - v[i]] + w[i]

綜上可得，

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

那麼，我們最終要求得的問題最終解即fn。

根據狀态計算，寫出代碼。

code

#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    const int N = 1010;
    int f[N][N] = {0};
    
    int n = 0;
    int m = 0;
    
    int v[N] = {0};
    int w[N] = {0};
    
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d %d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    
    printf("%d\n", f[n][m]);
    return 0;
}           

代碼優化

觀察上述代碼，我們不難發現，第一維數組f[i]，隻和f[i -1]相關，在周遊i的過程中，我們必先會求得f[i - 1]，故可以做等價變換，将i這個次元去掉，簡化代碼如下

#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    const int N = 1010;
    int f[N] = {0};
    
    int n = 0;
    int m = 0;
    
    int v[N] = {0};
    int w[N] = {0};
    
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d %d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    printf("%d\n", f[m]);
    return 0;
}