\[
x_n = \left\{\begin{matrix}
1 & , if \; w_1 \leq W \\
\frac{W}{w_1} & , if \; w1 > W \\
\end{matrix}\right.
\]
0-1 Knapsack problem
Input：
n 個物件
第 i 個重量為 \(w_i\) ，價值為 \(v_i\)。
背包最大負重
\(W\)
Output：
最大的獲利值
限制條件：
取得物品的總重量 \(\leq\) W
只能取物品的整體
想法
無法使用 Greedy method 解決
使用動態規劃解決，物品的重量必為正整數
遞迴結構：(令 \(C[i][k]\) 在負重 k 之下考慮物品 1 ... i 之最大獲利
\[
C[i][k] = \left\{\begin{matrix}
0 & , if \;i = 0\;OR\; k = 0 \\
max(C[i-1][k-w_i]+v_i, C[i-1][k] )& , if \; w_i \leq k \\
C[i-1][k] & , if \; w_i > k \\
\end{matrix}\right.
\]
Algorithm ( Bottom up )
1 2 3 4 5 6 7 8 9 10 11 12 13
for k <- 0 to w c[0, k] <- 0 for i <- 1 to n { c[i, 0] <- 0 for k <- 1 to w { if k < w_i c[i, k] <- c[i-1, k] else c[i, k] <- max(c[i-1, k], c[i-1, k-w_i]+v_i) } }
Time complexity
\(\Theta( nW )\)Pseudo-polynominal
Space complexity
\(\Theta( nW )\)
Branch and bound 解 0-1 Knapsack problem
對於一個 NP-Completed 問題來說，可以使用「Branch and bound」來解決
「Branch and bound」演算法中，「Bounding function」的設計會是影響整體效能最大的關鍵 ( 收斂快慢 )。
Time complexity：O( 葉節點個數 )
葉節點個數取決問題本身。
組合性問題：\(2^n\)
排列性問題：\(n!\)
將球最佳解的過程視為在一個「State space tree」中尋找最好的節點。
實務上，通常是設計一 個「Bounding function」以估計目前狀態可到最佳解的可能性。
建構「State space tree」時，每次都先展開「Bounding function」的節點。( Branch )
在每次展開的過程中，都可以得到一個目前最佳解 (葉節點)，接著，之後不展開「Bounding function 值\(\leq\)目前最佳解」的內部節點。( Bound )
for j <- 0 to n c[0, j] <- 0 for i <- 0 to m c[i, 0] <- 0 for i <- 1 to m for j <- 1 to n { if(X[i] = Y[i]) c[i, j] = c[i-1, j-1] + 1 else c[i, j] = max(c[i-1, j], c[i, j-1]) }
\[
m[i, j] = \left\{\begin{matrix}
0 & , if \;i \geq j\\
MIN_{i\leq k \leq j-1}(m[i, k] + m[k+1, j] + P_i\times P_k \times P_j) & , if \; i < j
\end{matrix}\right.
\]
演算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
for i <- 1 to n (「Matrix chain」長度為一) m[i, i] <- 0 for l <- 2 to n (「Matrix chain」長度為二以上) for i <- 1 to n-l+1 (起點) { j <- i+l-1 (終點) m[i, j] <- infinity for k <- i to j-1 { tmp <- m[i, k] + m[k+1, j] + P_i-1 * P_k * P_j if tmp < m[i, j] m[i, j] <- tmp (純量乘法數) s[i, j] <- k (切點) } }
We define the maximum subarray of an array A to be the nonempty, contiguous subarray of A whose value have the largest sum
Fill in the blank (a), (b) in the following c++ function so that it returns value are placed in A[1], A[2], …, A[n-1]
1 2 3 4 5 6 7 8 9 10 11 12 13
intmaxSubarray(int A[], int n){ for(int i = 1; i<n; ++i) { A[i] += A[i-1]; } int ans = A[0]; int k = 0; for(int i = 0; i<n; ++i) { ans = max(ans, (a) ); k = min(k, (b) ); } return ans; }
