揹包問題是軟件工程師面試中常問的問題，它被變形成許多問題用於考察面試者的思維能力. 揹包問題的思路主要是將複雜的問題劃分為子問題，先依次求解子問題，最終再求得原問題. 本文探究的揹包問題為 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 only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
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/揹包問題]
