背包：動態規劃 ### def knapsack_dp(wgt, val, cap) n = wgt.length # 初始化 dp 表 dp = Array.new(n + 1) { Array.new(cap + 1, 0) } # 狀態轉移 for i in 1...(n + 1) for c in 1...(cap + 1) if wgt[i - 1] > c # 若超過背包容量，則不選物品 這兩種方案的較大值 dp[i][c] = [dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]].max end end end dp[n][cap] end 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 319 圖 14‑20 背包：空間最佳化後的動態規劃 ### def knapsack_dp_comp(wgt, val, cap) n = wgt.length # 初始化 dp 表 dp = Array.new(cap + 1, 0) # 狀態轉移 for i in 1...(n + 1) # 倒序走訪 for c in cap.downto(1) if wgt[i - 1] > c # 若超過背包容量，則不選物品

val: [Int], cap: Int) -> Int { let n = wgt.count // 初始化 dp 表 var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1) // 狀態轉移 for i in 1 ... n { for c in 1 ... cap { if wgt[i 這兩種方案的較大值 dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]) } } } return dp[n][cap] } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 324 第 14 章 knapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int { let n = wgt.count // 初始化 dp 表 var dp = Array(repeating: 0, count: cap + 1) // 狀態轉移 for i in 1 ... n { // 倒序走訪 for c in (1 ... cap).reversed() { if wgt[i

-> Vec { let cap = self.que_capacity; let mut j = self.front; let mut arr = vec![0; self.que_size as usize]; for i in 0..self.que_size { arr[i as usize] = self.nums[(j % cap) as usize]; j += knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 { let n = wgt.len(); // 初始化 dp 表 let mut dp = vec![vec![0; cap + 1]; n + 1]; // 狀態轉移 for i in 1..=n { for c in 1..=cap { if wgt[i - 1] > c as i32 { std::cmp::max( dp[i - 1][c], dp[i - 1][c - wgt[i - 1] as usize] + val[i - 1], ); } } } dp[n][cap] } 第 14 章 動態規劃 www.hello‑algo.com 334 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章

KnapsackDP(int[] weight, int[] val, int cap) { int n = weight.Length; // 初始化 dp 表 int[,] dp = new int[n + 1, cap + 1]; // 狀態轉移 for (int i = 1; i <= n; i++) { for (int c = 1; c <= cap; c++) { if (weight[i - 1] dp[i, c] = Math.Max(dp[i - 1, c - weight[i - 1]] + val[i - 1], dp[i - 1, c]); } } } return dp[n, cap]; } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 325 第 14 KnapsackDPComp(int[] weight, int[] val, int cap) { int n = weight.Length; // 初始化 dp 表 int[] dp = new int[cap + 1]; // 狀態轉移 for (int i = 1; i <= n; i++) { // 倒序走訪 for (int c = cap; c > 0; c--) { if (weight[i -

val, int cap) { int n = wgt.length; // 初始化 dp 表 List> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0)); // 狀態轉移 for (int i = 1; i <= n; i++) { for (int c = 1; c <= cap; c++) { 這兩種方案的較大值 dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]); } } } return dp[n][cap]; } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 324 第 14 wgt, List val, int cap) { int n = wgt.length; // 初始化 dp 表 List dp = List.filled(cap + 1, 0); // 狀態轉移 for (int i = 1; i <= n; i++) { // 倒序走訪 for (int c = cap; c >= 1; c--) { if (wgt[i

knapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int { val n = wgt.size // 初始化 dp 表 val dp = Array(n + 1) { IntArray(cap + 1) } // 狀態轉移 for (i in 1..n) { for (c in 1..cap) { if (wgt[i - 1] > c) { // 若超過背包容量，則不選物品 這兩種方案的較大值 dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + _val[i - 1]) } } } return dp[n][cap] } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 328 圖 14‑20 knapsackDPComp(wgt: IntArray, _val: IntArray, cap: Int): Int { val n = wgt.size // 初始化 dp 表 val dp = IntArray(cap + 1) // 狀態轉移 for (i in 1..n) { // 倒序走訪 for (c in cap downTo 1) { if (wgt[i - 1] <= c) {

knapsackDP(int[] wgt, int[] val, int cap) { int n = wgt.length; // 初始化 dp 表 int[][] dp = new int[n + 1][cap + 1]; // 狀態轉移 for (int i = 1; i <= n; i++) { for (int c = 1; c <= cap; c++) { if (wgt[i - 1] > c) dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]); } } } return dp[n][cap]; } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 325 第 14 knapsackDPComp(int[] wgt, int[] val, int cap) { int n = wgt.length; // 初始化 dp 表 int[] dp = new int[cap + 1]; // 狀態轉移 for (int i = 1; i <= n; i++) { // 倒序走訪 for (int c = cap; c >= 1; c--) { if (wgt[i - 1]

knapsackDP(wgt, val, cap) { const n = wgt.length; // 初始化 dp 表 const dp = Array(n + 1) .fill(0) .map(() => Array(cap + 1).fill(0)); // 狀態轉移 for (let i = 1; i <= n; i++) { for (let c = 1; c <= cap; c++) { if dp[i - 1][c - wgt[i - 1]] + val[i - 1] ); } } } 第 14 章 動態規劃 www.hello‑algo.com 324 return dp[n][cap]; } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 325 圖 14‑20 function knapsackDPComp(wgt, val, cap) { const n = wgt.length; // 初始化 dp 表 const dp = Array(cap + 1).fill(0); // 狀態轉移 for (let i = 1; i <= n; i++) { // 倒序走訪 for (let c = cap; c >= 1; c--) { if (wgt[i

Array, val: Array, cap: number ): number { const n = wgt.length; // 初始化 dp 表 const dp = Array.from({ length: n + 1 }, () => Array.from({ length: cap + 1 }, () => 0) ); // 狀態轉移 for for (let i = 1; i <= n; i++) { for (let c = 1; c <= cap; c++) { if (wgt[i - 1] > c) { // 若超過背包容量，則不選物品 i dp[i][c] = dp[i - 1][c]; } else { // 不選和選物品 i 這兩種方案的較大值 dp[i][c] = Math.max( dp[i - 1][c] 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1] ); } } } return dp[n][cap]; } 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 329 第 14 章 動態規劃 www.hello‑algo.com 330

val: list[int], cap: int) -> int: """0-1 背包：動態規劃""" n = len(wgt) # 初始化 dp 表 dp = [[0] * (cap + 1) for _ in range(n + 1)] # 狀態轉移 for i in range(1, n + 1): for c in range(1, cap + 1): if wgt[i - 不選和選物品 i 這兩種方案的較大值 dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]) return dp[n][cap] 如圖 14‑20 所示，時間複雜度和空間複雜度都由陣列 dp 大小決定，即 ?(? × ???) 。 第 14 章 動態規劃 www.hello‑algo.com 311 第 14 章 動態規劃 list[int], val: list[int], cap: int) -> int: """0-1 背包：空間最佳化後的動態規劃""" n = len(wgt) # 初始化 dp 表 dp = [0] * (cap + 1) # 狀態轉移 for i in range(1, n + 1): # 倒序走訪 for c in range(cap, 0, -1): if wgt[i - 1]