前言

有名的背包問題是說，有一個固定重量的背包，和幾件不同重量不同價值的物品，在不超過背包重量的情況，將這些物品放到背包的最佳解(達到最大價值)是多少

背包問題又有好幾種變形

1. fractional knapsack

每樣物品可切割

此情況是最簡單的，可以用 Greedy 解決

先計算物品價值與重量的比值，會得到每個物品在1個單位的重量的價值，每次取比值最大的物品先塞入背包，

假如有3樣物品

1
2
3
A (5 kg, 10 value)
B (6 kg, 6 value)
C (7kg, 21 value)

先計算價值與重量的比值會得到

1
2
3
A = 2 value / 1kg
B = 1 value / 1kg
C = 3 value / 1kg

Greedy Example

背包重量為15kg

選擇比值最大的C先塞
因為背包重量大於C的整體重量，所以可以將C全部放入，15 - 7 = 8
背包重量剩8kg，價值為0 + 21 = 21

因為背包還沒滿，選擇第二大的 A 放入
背包剩餘的重量大於A的整體重量，所以可以將 A 全部放入，8 - 5 = 3
背包重量剩 3kg，價值為 21 + 10 = 31

繼續放，B沒辦法全部放入，只能放 3kg 的 B

最後總價值為31 + 3 = 34

背包重量為6kg

放 6kg 的 C，3 value * 6, 總價值為 18

2. discrete knapsack

每樣物品不可分割

沒辦法用greedy的方式解決，因為每樣物品不可分割，先放入價值較高的物品到背包可能會造成空間不必要的浪費，反而不是最佳解

discrete knapsack 又有分可以重複放同一件物品或是每件物品不能重複放的情況

  • with repetition
  • without repetition

Greedy Example

背包重量13kg

1
2
3
4
5
6
7
A(8kg, 12 value)
B(6kg, 6 value)
C(7kg, 7 value)

A = 1.5 value / 1kg
B = 1 value / 1kg
C = 1 value / 1kg

用 Greedy 的方式會先選擇 A，全部放入後，背包重量變 5kg，價值 12
但 5kg 無法再放入 B 或 C，總價值最後為 12，這不是最佳解

最佳解應為，放 B 之後再放 C，總價值為 13

這類型的背包問題是屬於 NP-complete，無法快速求得精確解，只能折衷求得近似解
但是如果N不大的情況下可以用 DP 得到最佳解

With Repetition

可以重複放同一件物品

假設有一最佳解 W 含有 Wi 個重量
如果把 Wi 拿掉，會得到 W-Wi 的最佳解 (cut and paste trick)

這句話可以想像成一個背包已經是最佳解的情況，重量是W
把其中一個物品拿出來，這個背包的重量變成(W - 該物品重量)，在這個重量之下的背包還是處於最佳解

概念：
Let value(w) be the maximum value of knapsack of weight w

value(w) = max{value(w - wi) + vi}

Example

1
2
3
4
5
6
7
W = 10 

// (value, weight)
($30, 6) ($14, 3) ($16, 4) ($9, 2)

w = [6, 3, 4, 2]
v = [30, 14, 16, 9]
1
2
3
4
5
6
7
8
9
10
Knapsack(W)
value(0) ← 0    // 一維陣列, 大小為背包重量上限 W+1
for w from 1 to W:
   value(w) ← 0   // 先把每個重量 1~W 填0
   for i from 1 to n:
      if wi <= w:
         val ← value(w - wi) + vi
         if val > value(w):
            value(w) ← val
return value(W)

直接看例子圖解會比較快理解
開 W+1 大小的陣列，運用 DP 的概念逐漸填滿，陣列最後一個數值就是最佳解
每一格是放最佳解，所以 W[4] 會是 value 18，而不是 14

knapsack1

重點在第二層 for 迴圈裡面的 if，會逐一檢查 w[] 的值是否 <= 目前跑到的背包重量 (1~W)

此題的情況，直到外層 w 跑到 2 時 (weigh = 2 的物品)
第二層的 for 迴圈才開始進入 if 條件式

(i = 3時，w[3] = 2，wi <= w)

此時第二層的for迴圈在計算 value[2] 的值時只有一種可能 val = value[2 - 2] + 9

  • val > value[2] (初始值是0)
  • value[2] = 9

當外層w跑到3時，第二層的 for 迴圈會有兩次 if 的機會
就是發生在 w[1]=3 和 w[3]=2，這兩個都小於等於 w=3
這時候就會發生取最佳解的比較了

第一次 if 會先評估 w[1]

  • val = value[3-3] + 14
  • val > value[3]
  • value[3] = 14

第二次 if 評估 w[3]

  • val = value[3-2] + 9
  • val < value[3] , 不會update

所以value[3]的最佳解是14

以此類推下去就會慢慢推出value[10]的值

簡單來說就是考慮組合成 value[n] 的所有可能
要塞滿 n，可以從 n-k或是 n-h 再放重量 k 或是重量 h 的東西
(假設要塞的物品有 k 重量和 h 重量可選)

此時就要比較(value[n-k] + 重量k的value) 以及 (value[n-h] + 重量h的value)，哪個比較高

實作時可以把每樣物品的 weight 和 value 包在一個 structure 內，會比較直觀且好寫

Without Repetition

不能重複放同一件物品

考慮兩種情況，有包含 last item 或沒包含 (放 or 不放)

概念:
The i-th item is either used or not

value(i, w) = max{value(i-1, w-wi) + vi, value(i-1, w)} // 放或不放

這個情況的演算法 Coursera 的課是開二維陣列做 DP
但演算法筆記有展示用一維就能解的方法

不過基本上都需要雙層迴圈啦，只是一維看起來比較舒服

這邊我就直接放當初寫 Coursera 背包問題作業的 code，註解應該滿清楚了

若是正在修這門課的請尊重Coursera的榮譽協定，不要直接抄襲上傳!
If you are attending this class of Coursera please do not copy and paste the solution code. Respect to Coursera’s honor code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/* ------------------- knapsack without repetitions ----------------------- */
/* take as much gold as possible into your bag.
/* just one of each you can either take it or not (cannot take a fraction of a bar).
/* 1 <= W <= 10^4, 1 <= n <= 300, 0 <= w0,...,wn-1 <= 10^5
/* input format: capacity W and number n of bars of gold
/* output format: maximum weight of gold that fits W
/* ------------------------------------------------------------------------ */

/* 0/1 knapsack problem, c(n, w) = max(c(n-1, w), c(n-1, w-weight[n]) + cost[n])
   對某一件物品來說, 選擇放或不放, 
   一件物品放進背包, cost上升, 耐重下降, 
   不放就是原有的cost跟耐重都不變, 
   上述式子的意思是取放or不放後的c(n)最大值, 是背包問題中關鍵的式子 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int optimal_weight(int W, const vector<int> w){
    // use 1-D array from n to (n - weight) to fill the array
    vector<int> c(W+1);
    // 可用一維陣列由後面往前填數字, 節省使用DP的空間
    for(int i = 0; i < w.size(); ++i){
        // 選擇放與不放兩種情況中, c[j]的最大值
        // 需要注意的是j不可能由比第i個物品價值還小的地方填數字
        for(int j = W; j >= w[i]; --j){
            // in this problem, cost and weight is equal
            c[j] = max(c[j], c[j-w[i]] + w[i]);
        }
    }
    // c[W] is the maximum value of knapsack with W weight
    return c[W];
}

int main(){
    int n, W;
    cin >> W >> n;
    vector<int> w(n);
    for (int i = 0; i < n; i++){
        cin >> w[i];
    }
    cout << optimal_weight(W, w) << '\n';
}