0-1 揹包問題及 leetcode 416 題解

揹包問題是軟件工程師面試中常問的問題，它被變形成許多問題用於考察面試者的思維能力. 揹包問題的思路主要是將複雜的問題劃分為子問題，先依次求解子問題，最終再求得原問題. 本文探究的揹包問題為 0-1 揹包問題，並解析 leetcode 416.

【0-1】揹包問題

1. 揹包問題

1.1 題目描述

<code>有 N 種物品和一個容量為 V 的揹包。第 i 種物品最多有n件可用，每件體積是c，價值是 w . 求解將哪些物品裝入揹包可使這些物品的體積總和不超過揹包容量，且價值總和最大./<code>

1.2 解題思路

這個問題最簡答的思路就是窮舉法, 另一個方法是動態規劃, 依次求解子問題.

窮舉法: 最基礎的思路，可以嘗試各種商品的組合，然後選出揹包內價值最大的組合. 通過這種思路，每個物品都有放入揹包、不放入揹包兩種選項，總的組合數量是 2^n . 時間複雜度是 o(2^n). 這樣的指數型時間複雜度顯然在工程上是不可取的.

動態規劃: 這個題目可以考慮使用動態規劃法，先解決局部的子問題，再解決最終的問題. 動態規劃問題的核心是找到動態規劃方程式，用於將問題劃分成子問題. 下面是分析思路.

容量為 v 的揹包，可以劃分為兩個容量為 v1 + v2 = v 的揹包組合. 這兩個揹包的組合的價值和可能是容量為 v 的揹包最大價值的潛在答案之一，v1、v2 依次分解成小容量揹包，就可以反向遞推容量為 v 的揹包問題的解了. 那麼如何將容量為 v 的揹包進行劃分呢？

可以考慮依次將第 i 個( i 從 1 到 n 遍歷)物品拿出來，它的體積是 ci . 此時選擇是否將物品放入揹包. 那麼就有兩種可能， 放入該物品和不放入該物品. 放入該物品的話，需要確保揹包容量足夠，不放入該物品，則當前的揹包最大價值與第 i-1 個物品取出時的情況相同.

比較這兩種情況得到的價值，若揹包中放入物品價值更大且容量滿足，則第 i 個物品時，揹包的最優解是放入物品 i. 否則第 i 個物品取出的最優解等同於第 i-1 個物品取出的情況.

在計算放入第 i 個物品時揹包的最大價值時，需要知道容量為揹包容量為 v - ci 的子問題揹包的最大價值.

這個問題的劃分思路是，計算放入第 i 個物品時，依次計算揹包容量為 1～v 時的最優解. 最終計算到第 n 個物品時，容量為 v 的最優解就是原題目的最終解. 動態規劃的方程式為如下:

動態規劃方程式

上述公式中 dp[i][j] 代表前 i 個物品, 揹包容量為 j 時揹包問題的最有解, 其中 0 <= i < n, 0 <= j <= v. ci 為物品 i 的體積，v[i] 為物品 i 的價值.

代碼實現如下:

<code>// golang 實現 //動態規劃 func backpack(capacities []int, values []int, capacity int) int { dp := make([][]int, len(values)) for i := 0; i < len(values); i++ { dp[i] = make([]int, capacity+1) } // 只有一個物品時，揹包問題的 dp[0] 解 for i := capacities[0]; i < capacity; i++ { dp[0][i] = values[0] } for i := 1 ; i < len(values); i++ { for j := 0;j <= capacity; j++ { if j < capacities[i] || dp[i-1][j] >= values[i] + dp[i][j - capacities[i]] { dp[i][j] = dp[i-1][j] }else { dp[i][j] = values[i] + dp[i][j - capacities[i]] } } } return dp[len(values)-1][capacity] }/<code>

2. leetcode 416 Partition Equal Subset Sum 及題解

揹包問題作為經典問題，它的解題思路被應用在許多問題上. 是面試中常問的問題. 其中 Leetcode 416 的解題思路就是揹包問題. 實際上，leetcode 416 是更簡單的揹包問題.

2.1 題目描述

Given a non-empty array containing

Note:

Example 1:

<code>Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]./<code>

Example 2:

<code>Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets./<code>

題目大意是給予一個正整數數組，判斷是否可以將數組分為兩個子數組，且兩個子數組的和是相等的.

2.2 題目求解

這道題和揹包問題一樣，可以採用窮舉法，列出所有的組合，但是時間複雜度太高，工程上是不可行的. 另一種方法也是動態規劃，可以將其劃分為子問題，先求子問題，在逐步求解原問題.

實際上，這道題可以通過將揹包容量設置為 sum/2 ，每個數的大小作為物品的體積，這題的最優解不需要考慮物品的價值，而是能否將揹包填滿. 事實上，它比揹包問題更簡單. 它只有一個體積，子問題即容量為 0 ~ sum/2 的揹包是否能夠被前 i 個物品的組合正好填滿.

我們設 dp[i] 為容量為 i 的揹包能否被前 j 個物品的組合正好填滿, nums[j] 為物品的體積. 則動態規劃方程式為:

dp[i] = dp[i-j]

以下是代碼實現:

<code>// golang 實現 func canPartition(nums []int) bool { var sum int for _, num := range nums { sum += num } // sum/2 有小數，nums 都為正數，顯然不可以 if sum % 2 == 1 { return false } sum = sum / 2 // 目標 target dp := make([]bool, sum+1) dp[0] = true for _, v := range nums { // 加入體積為 v 的數後，重新判斷容量為 v ~ sum 的揹包是否能被填滿 for j := sum; j > 0; j-- { if j >= v && dp[j-v] { dp[j] = true } } } return dp[sum] }/<code>

3. END

3.1 其它

0-1 揹包問題是揹包問題的其中一種，揹包問題可以劃分為三類，包括: 0-1 揹包問題、完全揹包問題、多重揹包問題. 它們是動態規劃的經典問題.

揹包可以出現在各領域的現實世界的決策過程，如資產證券化、投資組合、選擇投資等. 揹包問題除了在面試中常常出現，也是是十分值得去探索的問題，它已經被研究超過了 1 個世紀.

3.2 參考文獻

1. 0-1 揹包問題 [https://www.jianshu.com/p/a66d5ce49df5]

2. partition equal subset sum [https://leetcode.com/problems/partition-equal-subset-sum/]

3.揹包問題 [https://baike.baidu.com/item/揹包問題]