0/1 背包問題

簡介

#

knapsack problem，中文稱「背包問題」（我覺得叫包包問題也不錯），根據維基百科的介紹，「背包問題」這個詞彙可以追朔到 1897 年的數學家-托比阿斯·丹齊格 （Tobias Dantzig）的研究。

背包問題是啥？為什麼不叫小籠包問題？

#

背包問題假設存在一個可以裝進任何物品的背包（所以你要裝一頭大象或是搞人口拐賣都行），但是有一個條件，背包有重量限制，背包不能裝超過重量負荷的物品，舉個例子： 假設有一個耐重 10 kg 的包包，有以下物品要裝進包包裡面

要想辦法在不超過耐重限制下，將這些東西裝進包包裡，且總價值要是所有可能組合裡最大的；相信以上面的例子使用肉眼很輕鬆的就可以看出要選擇 ID 為 ‘1’ 、‘3’、 ‘4’ 的物品，總價值會最大。

背包問題的各種變形

#

就像裙子有分百褶裙、蛋糕裙、蓬蓬裙一樣，背包問題有多種不同的變形，其中最基本的是 0 / 1 背包問題，所謂 0 / 1 背包問題指的是物品要碼放進背包 0 個，要碼放 1 個；換句話就是每件物品可以選擇放進背包或不放進背包一次（注意：是 1 次）。 與 0 / 1 背包問題對應的叫無限背包問題（Unbounded Knapsack），在無限背包問題的世界觀裡，物品是會自我繁殖的，所以可以無限拿，拿到滿意為止。 剩下的還有多重背包（Bounded Knapsack)、分數背包（Fractional Knapsack）、**多維背包（Multi-dimensional Knapsack)**等名子聽起來很酷(恐)炫(怖)的背包問題。

NP-complete 問題

#

背包問題屬於 NP-complete （NP 完備問題），NP 完備（NP-Complete） 可以直接理解成描述某些「非常難解」的問題。

註：我也不知道 NP-complete 具體上是甚麼意思

攻略 0 / 1 背包問題

#

這是從這裡看到的說明：

先建一個列數為物品數 + 1，行數為耐重 + 1 的二維陣列，然後裡面全填 0 假設有 n 個物品，背包耐重為 w ，程式應該會長這樣 :

vector<vector<int>> dp (n + 1,vecotr(w + 1,0))

拿上面有小籠包的案例畫成表格 : 其中:

• 1~5 代表 1~5 物品
• 1~10 代表耐重力為 1~10 的情況
• 表格內容則是耐重力為 X kg 時，考慮第 Y 號物品的最大價值

我們要找耐重為 10 kg 時的最大價值，但我們不從 10 kg 開始看，而是從 1 kg 開始看，像蓋建築一樣慢慢疊上去。

直接看座標 1 - 1 那一格是甚麼意思 ? ( 列 - 行 )

• 它代表耐重為 1 kg 時，放第 1 個物品時的最大價值是多少 ? 第 1 個物品小籠包重達 2 kg 所以放不進去，因此此時的最大價值是耐重為 1 kg 放第 0 個物品時的最大價值 ( 等價於不放物品進去 )，所以是 0。
• 第 1 - 2 代表耐重為 2 kg 時，放第 1 個物品時的最大價值是多少 ? 這個時候重達 2 kg 的小籠包剛好放的進去，所以此時的最大價值就是小籠包的價值，也就是 1145 USD，按照這樣的邏輯，第 1 列剩下的都會是 1145 USD。

把數字填到表裡會長這樣，看起來非常合理，只放小籠包，最大價值是 1145 USD，如果題目只有 1 個物品（當然不可能）那這就是答案了，完結撒花~🎉

• 來看 2 - 1，2 - 1 是甚麼意思? 2 - 1 代表耐重為 1kg 時，把 2 號物品宣傳單放到背包裡，但是 2 號物品重達驚人的 7 kg 所以放不進去，因此只能選擇不放，由於沒有放東西，所以最大價值會是 1 - 1。
• 2 - 2，代表想要把耐重為 2 kg 把 7 kg 的宣傳當放進去，但放不進去，所以此時的最大價值會是 1 - 2，接下來我們直接看到 2-7。
• 2-7，太棒了，耐重為 7 kg，所以放的下 2 號物品，因為放了 7 kg 的物品所以耐重力會減 7，所以選擇 1-0 ( 7-7=0 ) 那一格的數值加上 2 號物品的價值，得到 14 USD；你也可以理解成放了 2 號物品耐重力變為 0。但是!!!!，如果選擇不放 2 號號物品會怎麼樣呢 ? 它會繼承 1-7 的數值也就是 1145 USD，我們要找最大的價值，所以實際上會選擇不放，最終結果填上 1145。
• 跳到 2-9，放入 2 號物品，選擇1 - 2 的數值加上 2 號物品價值，得到1159，可以理解成放了 2 號物品還有額度讓你再放 1 號物品進去。如果不放則只有 1145 USD，所以當然是選擇要放，得到1159。

• 3-1 ，看到 3 號物品黃仁勳的力量，重 5 kg 價值 2000 USD，但很遺憾的，它要耐重力為 5 才放的進去，所以我們直接看到 3-5
• 3-5，放入黃仁勳的力量，耐重力 5-5 = 0，因此從 2-0 加上 2000 USD，所以最終是 2000 USD
• 3-7，放入力量，得到 2-2 的1145 + 2000 = 31145，沒意外的話，剩下的都是 31145

• 四號物品，狗狗幣重 3 Kg，直接看到 4-3，放入狗狗幣 3-0 加上 200 USD ，但比不放狗狗幣的 1145 USD 還小，所以選擇不放。
• 來到 4-5，放入狗狗幣 3-2 加上 200 得到 1345，但若選擇不放可拿 2000，所以選擇不放。
• 來到 4-8，放入狗狗幣 3-5 加上 200 得到 2200，但不放有 3145 USD，所以選擇不放。
• 來到 4-10，放入狗狗幣 3-7 加上 200 得到 3345，比不放 3145 USD 還大，所以選擇放入。

五號，垃圾，6 Kg ，價值 800USD

• 直接看到 5-5，放入垃圾，4-0 加上 500，得到 500，但不放有 1145，所選不放。
• 5-7，放入垃圾，4-2 加上 500，得到 1645，但不放有 3145，所以不放
• 5-10，放入垃圾， 4-5 加上 500，得到2500，但不放有 3345，所以選擇不放

表格填完後，最右下角的 3345 就是我們要的答案啦~它代表的意思是 「耐重為 10 的情況下，考慮第 1 號到第 5 號物品的最大價值」

來看一些很複雜的數學… 背包問題可以寫成一個遞迴式 :

\((n , w)\) 代表耐重為 \(w\) 時，考慮第 0 到 第 n 個物品時的最大價值 來看 \(max\) 裡的東西 :

• \(c(n-1,w)\) 代表不放東西到背包；意思是考慮第 0 個物品到第 n-1 個物品的最大價值，因為沒有東西到背包中，所以耐重和 \(n-1\) 一樣還是 \(w\)。
• \(c(n-1,w-weight[n])+cost[n]\) 代表有放東西到背包中； 因為放了東西到背包，所以耐重 \(w\) 要減掉第 \(n\) 個物品的重量， \(c(n-1,w-weight[n])\) 代表考慮第 0 到 \(n-1\) 個物品並且耐重為 \(w-weight[n]\) 時的最大價值，最後再加上第 n 個物品的價值 \(cost[n]\) ，整體得到放進第 \(n\) 個物品時的價值 ( 注意 : 不一定是最大價值 ) 用一句話總結，就是放第 0 到 第 n 個物品的最大價值，是不放或要放第 n 個物品，取價值最大的那一個。

題目實戰

#

我們來看看這題 UVA 990 關於一位老兄潛水找寶藏的故事。 故事是這樣的，一位叫 John 的老兄潛水打撈寶藏，但很不幸的 John 只有一個氣瓶，所以他必須在一個氣瓶的容量內打撈出總價值最高的寶藏 ; 總之，聽起來是一個吐槽點很多的故事，使用一堆文字讓我們這群英文苦手看了膽驚受怕 ^^。

題目有一些參數 :

1. 有 n 個寶藏，每個寶藏有 2 個屬性 : 深度 (\(d_i\)) 和 寶藏價值 (\(v_i\))
2. 氣瓶可以撐 \(t\) 秒
3. 收集每個寶藏所需的時間 = \(下潛時間 + 上浮時間\) = \(w × d_i + 2w × d_i\) = \(3w × d_i\) , 其中 w 是常數，題目會給

整個題目都沒有 “背包” 兩個字的影子，對吧 ! 但其實它是一個 0/1 背包問題，讓我們換個角度看題目~

• 背包耐重 : 氣瓶可以撐 t 秒
• 物品數量 : \(n\) 個寶藏
• 物品價值 : 寶藏價值 (\(v_i\))
• 物品重量 : 收集每個寶藏所需的時間，也就是 \(3w × d_i\)

題目輸入 : 先給 \(t\) 和 \(w\) 接著給 \(n\) 接下來有 \(n) 筆資料要輸入，每筆有兩個值 : (\(d_i,v_i\))

題目輸出 :

1. 可以獲得的最大價值
2. 找到幾個寶藏
3. 找到的每筆寶藏深度和價值

開始需要設定這些變數

        vector<int>money; //每筆寶藏的價值
        vector<int>weights;//每筆寶藏的重量
        vector<int>depths;//深度
        vector<vector<int>>dp;//神聖的 DP 表格
        vector<int>selected;//選擇的寶藏
		int maxMoney;//最大價值
        int treasure_count = n;//寶藏數

再處理輸入 比較要注意的地方是

1. 因為 n 在迴圈會被殺掉，所以要先把它複製起來
2. 深度因為題目最後會要求輸出出來，所以要存起來

	cin >> t >> w >> n; // t 是氣瓶容量
	while (n--) {
		cin >> d >> v; //d 是深度 v 是價值
		money.push_back(v);
		depths.push_back(d);
		weights.push_back(3*w*d);
	}

接著來到重點部分 : 填背包問題的表 先建個函數

函數輸入 :

1. 氣瓶容量 (耐重)
2. 寶藏數 (物品數)
3. 寶藏價值 (物品價值)
4. 撈每個寶藏需要的下潛加上浮時間 (物品重量)
5. DP 陣列

輸出 : 可獲得的寶藏最大價值 接下來為了統一，我都用「耐重」 「物品」等名詞來解釋，而不是氣瓶容量、寶藏數那些

int solve(int t,int n,vector<int>& money,vector<int>& weights, vector<vector<int>>& dp)

在函數內部使用 resize 對 dp 陣列改變成 「物品數 + 1」個列 「耐重 + 1」個行，並且全部填 0

dp.resize(n+1, vector<int>(t+1,0));

使用雙迴圈遍歷整個陣列 注意是從 1 開始並且使用 “<=”

for(int i=1 ; i<=n ; ++i){
	for(int j=1 ; j<=t ; ++j){
		...
	}
}

迴圈內加入這一段 : 它的意思是如果目前的耐重無法支撐物品的重量，那就不放，此時最大價值會是考慮前一個物品時的最大價值

if(j < weights[i-1])
	dp[i][j] = dp[i-1][j];

if 下面再加 else 上去 意思是如果當前耐重可以承受這個物品的重量，那就從 「不放物品」 和 「放物品」 兩個取最大的那一個 ; 「放物品」 的程式看起來複雜一點，它的涵義是找到 「前一個物品」耐重是 「當前耐重 - 物品重量」時的最大價值再加上「當前物品價值」。 這邊要注意的地方是 weights 和 money 兩個陣列是從 0 開始算起，所以要減 1

if(j < weights[i-1])
	dp[i][j] = dp[i-1][j];
else
	dp[i][j] = max(dp[i-1][j],dp[i-1][t-weights[i-1]] + money[i-1]);

最後合起來會是這樣，但別忘了要回傳答案，答案很簡單，就是陣列的最右下角，即 dp[n][t]

int solve(int t,int n,vector<int>& money,vector<int>& weights, vector<vector<int>>& dp)
{
    dp.resize(n+1, vector<int>(t+1,0));
    
    for(int i=1 ; i<=n ; ++i){
        for(int j=1 ; j<=t ; ++j)
        {
            if(j < weights[i-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i-1]] + money[i-1]);
        }
    }  
	return dp[n][t];
}

回顧一下題目在問甚麼 ?

1. 可以獲得的最大價值
2. 找到幾個寶藏 (放了哪個物品到背包?)
3. 找到的每筆寶藏深度和價值 (各個放入背包的物品價值)

現在解決了「可以獲得的最大價值」，接著把 2、3 點一起解決

0 / 1 背包問題回朔

#

要解決第 2、3 點，我們先看一下前面建的表

我們要找的是究竟放了哪些物品到背包有最大價值

• 所以先從耐重最大，最後一個物品開始看 ( 5-10 )，一直往上找到「上一列 (物品) 第目前耐重減去目前物品重量行加上目前物品價值等於自己」的那一格。
• 5-10 的 3345，因為它的前一列為 4 號，目前耐重 10 減去 5 號重量 3 等於 4，看到 4 - 4，4-4 的 1145 加上 5 號的價值 800不等於 3345，所以建表時沒有放入 5 號物品。
• 4-10 的 3345，因為它的前一列為 3 號，目前耐重 10 減去 4 號重量 3 等於 7，看到 3 - 7，3-7 的 3145 加上 4 號的價值 200 剛好等於 3345，所以建表時有放入 4 號物品。
• 我們知道已經放入 4 號物品，所以接下來要看「放入 4 號物品後」放了哪些物品 ; 把目前的耐重減掉 4 號物品的重量，並且往上移一列就可以得到放入 4 號物品時的狀態，也就是 3-7。你也可以想成放了四號物品最大耐重變成 7 ，要找耐重為 7 時放了那些物品有最大價值。
• 3-7 的 3145，因為它的前一列為 2 號，目前耐重 7 減去 3 號重量 5 等於 2，看到 2 - 2，2-4 的 1145 加上 3 號的價值 2000 剛好等於 3345，所以建表時有放入 5 號物品。
• 2-2 的 1145，因為它的前一列為 1 號，目前耐重 2 ，而 2 號重量 7 會放不下，所以跳過。
• 1-2 的 1145，因為它的前一列為 0 號，目前耐重 2 減去 1 號重量 2 等於 0，看到 0 - 0，0-0 的 0 加上 1 號的價值 1145 剛好等於 145，所以建表時有放入 1 號物品。

最後寫成程式是這樣 需要注意的地方是迴圈的條件是 「i>0 && t >0」 防止越界 中間的 if 判斷式為了避免 2-2 的狀況發生，要加上 t >= weights[i-1] 最後的 selected 要用 reverse 把它反轉

vector<int> getSelectedItems(int t,int n,vector<vector<int>>&dp,vector<int>&weights,vector<int>&money){

    vector<int>selected;
    for(int i=n ; i>0 && t >0 ; --i){
        if(t >= weights[i-1] && dp[i][t] == dp[i-1][t-weights[i-1]] + money[i-1])
        {
            selected.push_back(i-1);
            t -= weights[i-1];
        }
    }
    
    reverse(selected.begin(),selected.end());
    return selected;
}

最後的最後把它們拼湊起來 注意 : 題目要求每筆 Case 間要空一行空白行，不能多空，不然會雖然答案是對的，但判斷是錯的

##include<iostream>
##include<vector>
##include<algorithm>
using namespace std;

int solve(int,int,vector<int>& ,vector<int>&, vector<vector<int>>&);
vector<int> getSelectedItems(int,int,vector<vector<int>>&,vector<int>&,vector<int>&);

int main(){
    int t,w,n,v,d;//題目給予參數
     bool first = true;

    while(cin >> t >> w >> n){
        if(!first)cout<<endl;
        first=false;

        vector<int>money; //每筆寶藏的價值
        vector<int>weights;//每筆寶藏的重量
        vector<int>depths;//深度
        vector<vector<int>>dp;//神聖的 DP 表格
        vector<int>selected;//選擇的寶藏
        int maxMoney;//最大價值
        int treasure_count = n;//寶藏數

        while (n--) {
            cin >> d >> v;
            money.push_back(v);
            depths.push_back(d);
            weights.push_back(3*w*d);
        }

        maxMoney = solve(t,treasure_count,money,weights,dp);    
        selected = getSelectedItems(t,treasure_count,dp,weights,money);

        cout<<maxMoney<<endl;
        cout<<selected.size()<<endl;

        for(auto k: selected){
            cout<<depths[k]<<" "<<money[k]<<endl;
        }
    }
}

int solve(int t,int n,vector<int>& money,vector<int>& weights, vector<vector<int>>& dp)
{
    dp.resize(n+1, vector<int>(t+1,0));

    for(int i=1 ; i<=n ; ++i){
        for(int j=1 ; j<=t ; ++j)
        {
            if(j < weights[i-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i-1]] + money[i-1]);
        }
    }
    return dp[n][t];
}

vector<int> getSelectedItems(int t,int n,vector<vector<int>>&dp,vector<int>&weights,vector<int>&money){
    vector<int>selected;
    for(int i=n ; i>0 && t >0 ; --i){
        if(t >= weights[i-1] && dp[i][t] == dp[i-1][t-weights[i-1]] + money[i-1])
        {
            selected.push_back(i-1);
            t -= weights[i-1];
        }
    }
    reverse(selected.begin(),selected.end());
    return selected;
}