14.5 完全背包問題¶
在本節中,我們先求解另一個常見的背包問題:完全背包,再瞭解它的一種特例:零錢兌換。
14.5.1 完全背包問題¶
Question
給定 \(n\) 個物品,第 \(i\) 個物品的重量為 \(wgt[i-1]\)、價值為 \(val[i-1]\) ,和一個容量為 \(cap\) 的背包。每個物品可以重複選取,問在限定背包容量下能放入物品的最大價值。示例如圖 14-22 所示。
圖 14-22 完全背包問題的示例資料
圖解 14-22:完全背包示例:物品可以重複選擇
完全背包允許重複選擇同類別物品;圖中給出容量 50 的最優選取方案。
給定 5 種候選物品,背包容量 cap = 50。每種物品的選取次數不限,總重量不能超過 50。本圖為容量 50 的獨立示例;後文圖 14-23 的單行更新改用容量 4、重量 1/2/3 的另一組部分同名、編號與重量都不同的物品資料。
畫面左側表格列出編號 i、重量 wgt[i-1] 與價值 val[i-1],各行用水果圖示標識物品。蘋果行以淺紫色、香蕉行以淺橙色突出,旁邊分別標“×1”“×2”,兩條箭頭指向右側標有“背包容量 cap = 50”的背包。下表把物品資料與圖示選取數量合併列出;其餘物品的 0 表示沒有被箭頭選中。
圖底明確標註“最大價值:290”,並用水果圖示說明放入一個蘋果和兩個香蕉,共佔用 50 背包容量。
| 編號 | 物品 | 重量 | 價值 | 圖示選取數量 |
|---|---|---|---|---|
| 1 | 蘋果 | 10 | 50 | 1 |
| 2 | 香蕉 | 20 | 120 | 2 |
| 3 | 葡萄 | 30 | 150 | 0 |
| 4 | 菠蘿 | 40 | 210 | 0 |
| 5 | 西瓜 | 50 | 240 | 0 |
由輸入補充計算:總重量為 10 + 2 × 20 = 50,總價值為 50 + 2 × 120 = 290,與圖底結論一致。若每件物品只能選一次,同一輸入的最優方案是香蕉加葡萄,重 20 + 30 = 50、值 120 + 150 = 270;這一對照由輸入推算,未畫在本圖中。允許重複選擇香蕉將最大價值提高到了 290。
1. 動態規劃思路¶
完全背包問題和 0-1 背包問題非常相似,區別僅在於不限制物品的選擇次數。
- 在 0-1 背包問題中,每種物品只有一個,因此將物品 \(i\) 放入背包後,只能從前 \(i-1\) 個物品中選擇。
- 在完全背包問題中,每種物品的數量是無限的,因此將物品 \(i\) 放入背包後,仍可以從前 \(i\) 個物品中選擇。
在完全背包問題的規定下,狀態 \([i, c]\) 的變化分為兩種情況。
- 不放入物品 \(i\) :與 0-1 背包問題相同,轉移至 \([i-1, c]\) 。
- 放入物品 \(i\) :與 0-1 背包問題不同,轉移至 \([i, c-wgt[i-1]]\) 。
從而狀態轉移方程變為:
2. 程式碼實現¶
對比兩道題目的程式碼,狀態轉移中有一處從 \(i-1\) 變為 \(i\) ,其餘完全一致:
def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
"""完全背包:動態規劃"""
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 - 1] > c:
# 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c]
else:
# 不選和選物品 i 這兩種方案的較大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
return dp[n][cap]
/* 完全背包:動態規劃 */
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// 初始化 dp 表
vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:動態規劃 */
int unboundedKnapsackDP(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) {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:動態規劃 */
int UnboundedKnapsackDP(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) {
// 若超過背包容量,則不選物品 i
dp[i, c] = dp[i - 1, c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i, c] = Math.Max(dp[i - 1, c], dp[i, c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n, cap];
}
/* 完全背包:動態規劃 */
func unboundedKnapsackDP(wgt, val []int, cap int) int {
n := len(wgt)
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, cap+1)
}
// 狀態轉移
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i-1][c]
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = int(math.Max(float64(dp[i-1][c]), float64(dp[i][c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[n][cap]
}
/* 完全背包:動態規劃 */
func unboundedKnapsackDP(wgt: [Int], 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 - 1] > c {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c]
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[n][cap]
}
/* 完全背包:動態規劃 */
function unboundedKnapsackDP(wgt, val, cap) {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// 狀態轉移
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],
dp[i][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
/* 完全背包:動態規劃 */
function unboundedKnapsackDP(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// 狀態轉移
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],
dp[i][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
/* 完全背包:動態規劃 */
int unboundedKnapsackDP(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// 初始化 dp 表
List<List<int>> 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++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:動態規劃 */
fn unbounded_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 {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = std::cmp::max(dp[i - 1][c], dp[i][c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:動態規劃 */
int unboundedKnapsackDP(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// 初始化 dp 表
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(cap + 1, sizeof(int));
}
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = myMax(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[n][cap];
// 釋放記憶體
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
return res;
}
/* 完全背包:動態規劃 */
fun unboundedKnapsackDP(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) {
// 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c]
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[n][cap]
}
### 完全背包:動態規劃 ###
def unbounded_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
# 若超過背包容量,則不選物品 i
dp[i][c] = dp[i - 1][c]
else
# 不選和選物品 i 這兩種方案的較大值
dp[i][c] = [dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[n][cap]
end
視覺化執行
3. 空間最佳化¶
由於當前狀態是從左邊和上邊的狀態轉移而來的,因此空間最佳化後應該對 \(dp\) 表中的每一行進行正序走訪。
這個走訪順序與 0-1 背包正好相反。請藉助圖 14-23 來理解兩者的區別。
圖 14-23 完全背包問題在空間最佳化後的動態規劃過程
圖解 14-23:完全背包的單行更新
按容量從小到大正序更新單行陣列,複用本輪較小容量的新解,使同種物品可以重複選取。
背包容量上限為 4,三種物品均可重複選取,具體重量和價值見下方“完全背包正序更新的物品輸入”表。本例從第 1 種物品蘋果已處理完畢開始,只演示第 2 種物品菠蘿這一輪,第 3 種物品西瓜尚未參與。
二維狀態 dp[i, c] 表示僅用前 i 種物品、總重量不超過容量 c 時的最大價值;空間最佳化後的單行陣列 dp[c](容量索引 c 從 0 至 4)按輪依次覆蓋上一輪結果。
第 i = 2 輪按容量 c = 1、2、3、4 正序走訪。容量不足以放入菠蘿(c < 2)時沿用上一輪舊值;裝得下時(c >= 2),比較不選菠蘿的舊值 dp[c] 與選入菠蘿的本輪值 dp[c - 2] + 11,取較大者寫入 dp[c]。較小正容量在本輪已先處理,容量 0 始終保持有效邊界 0,因此正序讀取本行左側的 dp[c - 2] 可以再次選入菠蘿,實現同種物品重複選取;0-1 背包每件限用一次、必須倒序讀取上一輪舊值的限制不適用於這裡。
畫面上方是二維表,下方是單行陣列;圖解按單行表、二維對照表的順序提供每步完整狀態,兩表名稱均含步號。單行表把數值與所屬輪次分列:i = 1 表示僅蘋果可選,i = 2 表示蘋果、菠蘿可選,不表示方案一定同時選入兩者。藍色表示上一輪狀態,綠色表示本輪已處理;收尾時本輪結果統一改藍,準備作為下一輪的舊狀態。二維表中“未計算初值”0 不能當作已算出的解。
| 編號i | 物品 | 重量 | 價值 |
|---|---|---|---|
| 1 | 蘋果 | 1 | 5 |
| 2 | 菠蘿 | 2 | 11 |
| 3 | 西瓜 | 3 | 15 |
走訪 i = 2 前:單行儲存 i = 1 的解
開始第 i = 2 輪(菠蘿)之前,第 1 輪(僅蘋果可選)已計算完畢:由於蘋果可重複選取,容量 0 至 4 依次放入 0 至 4 個蘋果,最大價值為 [0, 5, 10, 15, 20]。單行陣列 dp 當前儲存這組 i = 1 的解,準備從左到右正序處理第 2 種物品菠蘿。
完全背包第 1 步:走訪 i = 2 前:單行儲存 i = 1 的解——單行 dp:各容量的值與所屬輪次 容量 c 當前值 所屬輪次及可選範圍 0 0 各輪共享的容量 0 邊界 1 5 上一輪 i=1,僅蘋果可選,尚未覆蓋 2 10 上一輪 i=1,僅蘋果可選,尚未覆蓋 3 15 上一輪 i=1,僅蘋果可選,尚未覆蓋 4 20 上一輪 i=1,僅蘋果可選,尚未覆蓋 完全背包第 1 步:走訪 i = 2 前:單行儲存 i = 1 的解——二維對照表:各子問題的計算進度 可選物品 容量0 容量1 容量2 容量3 容量4 前0種物品 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 前1種物品 0,邊界有效 5,已計算 10,已計算 15,已計算 20,已計算 前2種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 前3種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 正序處理容量 c = 1:裝不下菠蘿,保持 5
從容量 c = 1 開始正序走訪:菠蘿重量 2 大於容量 1,無法放入菠蘿。二維對照表中 dp[2, 1] 直接繼承正上方 dp[1, 1] = 5;單行陣列的 dp[1] 數值保持 5,但所屬輪次已更新為本輪 i = 2(圖中以綠色標示本輪已處理),而容量 2 至 4 仍為上一輪 i = 1 的舊值。
完全背包第 2 步:正序處理容量 c = 1:裝不下菠蘿,保持 5——單行 dp:各容量的值與所屬輪次 容量 c 當前值 所屬輪次及可選範圍 0 0 各輪共享的容量 0 邊界 1 5 本輪 i=2,可選範圍:蘋果、菠蘿 2 10 上一輪 i=1,僅蘋果可選,尚未覆蓋 3 15 上一輪 i=1,僅蘋果可選,尚未覆蓋 4 20 上一輪 i=1,僅蘋果可選,尚未覆蓋 完全背包第 2 步:正序處理容量 c = 1:裝不下菠蘿,保持 5——二維對照表:各子問題的計算進度 可選物品 容量0 容量1 容量2 容量3 容量4 前0種物品 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 前1種物品 0,邊界有效 5,已計算 10,已計算 15,已計算 20,已計算 前2種物品 0,邊界有效 5,已計算 0,未計算初值 0,未計算初值 0,未計算初值 前3種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 正序更新容量 c = 2:選入 1 個菠蘿,更新為 11
向右正序推進到容量 c = 2:不選菠蘿時沿用上一輪舊值 dp[2] = 10(兩個蘋果);選入 1 個菠蘿時,讀取本行左側容量 0 的邊界狀態 dp[0] = 0 並加菠蘿價值 11,得 11。取 max(10, 11) = 11,將單行 dp[2] 更新為本輪新值 11。
完全背包第 3 步:正序更新容量 c = 2:選入 1 個菠蘿,更新為 11——單行 dp:各容量的值與所屬輪次 容量 c 當前值 所屬輪次及可選範圍 0 0 各輪共享的容量 0 邊界 1 5 本輪 i=2,可選範圍:蘋果、菠蘿 2 11 本輪 i=2,可選範圍:蘋果、菠蘿 3 15 上一輪 i=1,僅蘋果可選,尚未覆蓋 4 20 上一輪 i=1,僅蘋果可選,尚未覆蓋 完全背包第 3 步:正序更新容量 c = 2:選入 1 個菠蘿,更新為 11——二維對照表:各子問題的計算進度 可選物品 容量0 容量1 容量2 容量3 容量4 前0種物品 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 前1種物品 0,邊界有效 5,已計算 10,已計算 15,已計算 20,已計算 前2種物品 0,邊界有效 5,已計算 11,已計算 0,未計算初值 0,未計算初值 前3種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 正序更新容量 c = 3:蘋果加菠蘿,更新為 16
繼續正序推進到容量 c = 3:不選菠蘿時為上一輪舊值 dp[3] = 15(三個蘋果);選入 1 個菠蘿時,讀取本行左側已在本輪處理過的 dp[1] = 5(一個蘋果),加上菠蘿價值 11 得 16(一個蘋果加一個菠蘿)。取 max(15, 16) = 16,將 dp[3] 更新為 16。
完全背包第 4 步:正序更新容量 c = 3:蘋果加菠蘿,更新為 16——單行 dp:各容量的值與所屬輪次 容量 c 當前值 所屬輪次及可選範圍 0 0 各輪共享的容量 0 邊界 1 5 本輪 i=2,可選範圍:蘋果、菠蘿 2 11 本輪 i=2,可選範圍:蘋果、菠蘿 3 16 本輪 i=2,可選範圍:蘋果、菠蘿 4 20 上一輪 i=1,僅蘋果可選,尚未覆蓋 完全背包第 4 步:正序更新容量 c = 3:蘋果加菠蘿,更新為 16——二維對照表:各子問題的計算進度 可選物品 容量0 容量1 容量2 容量3 容量4 前0種物品 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 前1種物品 0,邊界有效 5,已計算 10,已計算 15,已計算 20,已計算 前2種物品 0,邊界有效 5,已計算 11,已計算 16,已計算 0,未計算初值 前3種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 正序更新容量 c = 4:複用本輪新值,重複選菠蘿得 22
正序推進到容量 c = 4:不選菠蘿時為上一輪舊值 dp[4] = 20(四個蘋果);選入菠蘿時,從本行左側讀取本輪剛更新過的 dp[2] = 11(已含 1 個菠蘿),再加 1 個菠蘿的價值 11 得到 22(共兩個菠蘿)。取 max(20, 22) = 22 寫入 dp[4],直接體現正序走訪允許複用本輪新解、重複選取同一種物品。
完全背包第 5 步:正序更新容量 c = 4:複用本輪新值,重複選菠蘿得 22——單行 dp:各容量的值與所屬輪次 容量 c 當前值 所屬輪次及可選範圍 0 0 各輪共享的容量 0 邊界 1 5 本輪 i=2,可選範圍:蘋果、菠蘿 2 11 本輪 i=2,可選範圍:蘋果、菠蘿 3 16 本輪 i=2,可選範圍:蘋果、菠蘿 4 22 本輪 i=2,可選範圍:蘋果、菠蘿 完全背包第 5 步:正序更新容量 c = 4:複用本輪新值,重複選菠蘿得 22——二維對照表:各子問題的計算進度 可選物品 容量0 容量1 容量2 容量3 容量4 前0種物品 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 前1種物品 0,邊界有效 5,已計算 10,已計算 15,已計算 20,已計算 前2種物品 0,邊界有效 5,已計算 11,已計算 16,已計算 22,已計算 前3種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 完成 i = 2 輪走訪:單行儲存前兩種物品的解
第 i = 2 輪正序走訪完成,單行 dp = [0, 5, 11, 16, 22] 儲存前兩種物品可選時容量 0 至 4 的最大價值。本步不再改寫數值,只將本輪結果統一改為藍色,作為下一輪的舊狀態。二維對照表“前3種物品”行在容量 1 至 4 的 0 仍為未計算初值,容量 0 保持邊界值 0;西瓜尚未開始處理。
完全背包第 6 步:完成 i = 2 輪走訪:單行儲存前兩種物品的解——單行 dp:各容量的值與所屬輪次 容量 c 當前值 所屬輪次及可選範圍 0 0 各輪共享的容量 0 邊界 1 5 本輪 i=2,可選範圍:蘋果、菠蘿;將作為下一輪舊狀態 2 11 本輪 i=2,可選範圍:蘋果、菠蘿;將作為下一輪舊狀態 3 16 本輪 i=2,可選範圍:蘋果、菠蘿;將作為下一輪舊狀態 4 22 本輪 i=2,可選範圍:蘋果、菠蘿;將作為下一輪舊狀態 完全背包第 6 步:完成 i = 2 輪走訪:單行儲存前兩種物品的解——二維對照表:各子問題的計算進度 可選物品 容量0 容量1 容量2 容量3 容量4 前0種物品 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 0,邊界有效 前1種物品 0,邊界有效 5,已計算 10,已計算 15,已計算 20,已計算 前2種物品 0,邊界有效 5,已計算 11,已計算 16,已計算 22,已計算 前3種物品 0,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值
按本例輸入補充對照:若誤用倒序,容量 4 會先於容量 2 處理,只能讀取舊值 dp[2] = 10,得到 max(20, 10 + 11) = 21,錯過兩個菠蘿的 22。這是從本例初始陣列推算的反例,未畫在圖中;它說明完全背包為何需要正序複用本輪新值。
程式碼實現比較簡單,僅需將陣列 dp 的第一維刪除:
def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
"""完全背包:空間最佳化後的動態規劃"""
n = len(wgt)
# 初始化 dp 表
dp = [0] * (cap + 1)
# 狀態轉移
for i in range(1, n + 1):
# 正序走訪
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# 若超過背包容量,則不選物品 i
dp[c] = dp[c]
else:
# 不選和選物品 i 這兩種方案的較大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap]
/* 完全背包:空間最佳化後的動態規劃 */
int unboundedKnapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// 初始化 dp 表
vector<int> dp(cap + 1, 0);
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空間最佳化後的動態規劃 */
int unboundedKnapsackDPComp(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 = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空間最佳化後的動態規劃 */
int UnboundedKnapsackDPComp(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 = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = Math.Max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空間最佳化後的動態規劃 */
func unboundedKnapsackDPComp(wgt, val []int, cap int) int {
n := len(wgt)
// 初始化 dp 表
dp := make([]int, cap+1)
// 狀態轉移
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c]
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = int(math.Max(float64(dp[c]), float64(dp[c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[cap]
}
/* 完全背包:空間最佳化後的動態規劃 */
func unboundedKnapsackDPComp(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 {
if wgt[i - 1] > c {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c]
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[cap]
}
/* 完全背包:空間最佳化後的動態規劃 */
function unboundedKnapsackDPComp(wgt, val, cap) {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: cap + 1 }, () => 0);
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空間最佳化後的動態規劃 */
function unboundedKnapsackDPComp(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: cap + 1 }, () => 0);
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空間最佳化後的動態規劃 */
int unboundedKnapsackDPComp(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// 初始化 dp 表
List<int> dp = List.filled(cap + 1, 0);
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空間最佳化後的動態規劃 */
fn unbounded_knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// 初始化 dp 表
let mut dp = vec![0; cap + 1];
// 狀態轉移
for i in 1..=n {
for c in 1..=cap {
if wgt[i - 1] > c as i32 {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
dp[cap]
}
/* 完全背包:空間最佳化後的動態規劃 */
int unboundedKnapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// 初始化 dp 表
int *dp = calloc(cap + 1, sizeof(int));
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c];
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[cap];
// 釋放記憶體
free(dp);
return res;
}
/* 完全背包:空間最佳化後的動態規劃 */
fun unboundedKnapsackDPComp(
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 1..cap) {
if (wgt[i - 1] > c) {
// 若超過背包容量,則不選物品 i
dp[c] = dp[c]
} else {
// 不選和選物品 i 這兩種方案的較大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[cap]
}
### 完全背包:空間最佳化後的動態規劃 ###
def unbounded_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 1...(cap + 1)
if wgt[i -1] > c
# 若超過背包容量,則不選物品 i
dp[c] = dp[c]
else
# 不選和選物品 i 這兩種方案的較大值
dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[cap]
end
視覺化執行
14.5.2 零錢兌換問題¶
背包問題是一大類動態規劃問題的代表,其擁有很多變種,例如零錢兌換問題。
Question
給定 \(n\) 種硬幣,第 \(i\) 種硬幣的面值為 \(coins[i - 1]\) ,目標金額為 \(amt\) ,每種硬幣可以重複選取,問能夠湊出目標金額的最少硬幣數量。如果無法湊出目標金額,則返回 \(-1\) 。示例如圖 14-24 所示。
圖 14-24 零錢兌換問題的示例資料
圖解 14-24:零錢兌換的最少硬幣數
圖示一種湊出金額 11 的最優選幣方案。
零錢兌換問題給定 3 種硬幣面值 coins = [1, 2, 5],每種面值的硬幣數量無限;本示例的目標金額為 amt = 11(注意與後續零錢兌換 II 示例的目標金額 5、以及動態規劃填表圖的目標金額 4 區分)。任務是求恰好湊出目標金額 11 所需的最少硬幣數量。
畫面左側表格列出編號 i 與面值 coins[i-1];面值 1 所在行以淺橙色、面值 5 所在行以淺綠色突出,兩條箭頭分別標註選 1 枚和選 2 枚,匯入右側標有“目標金額 amt = 11”的錢袋。面值 2 未選用。下表把這些高亮及箭頭關係整理為選用枚數。
圖底給出“最優硬幣組合:1 + 5 + 5”和“最少硬幣數量:3”。
| 編號i | 面值 | 圖中方案選用枚數 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 0 |
| 3 | 5 | 2 |
按圖中組合計算,1 + 5 + 5 = 11,共用 3 枚。補充最少性的理由:最大面值為 5,任意兩枚的總額至多為 5 + 5 = 10,小於 11,因此少於 3 枚無法完成;這一論證由輸入資料推得,未寫在原圖中。
1. 動態規劃思路¶
零錢兌換可以看作完全背包問題的一種特殊情況,兩者具有以下關聯與不同點。
- 兩道題可以相互轉換,“物品”對應“硬幣”、“物品重量”對應“硬幣面值”、“背包容量”對應“目標金額”。
- 最佳化目標相反,完全背包問題是要最大化物品價值,零錢兌換問題是要最小化硬幣數量。
- 完全背包問題是求“不超過”背包容量下的解,零錢兌換是求“恰好”湊到目標金額的解。
第一步:思考每輪的決策,定義狀態,從而得到 \(dp\) 表
狀態 \([i, a]\) 對應的子問題為:前 \(i\) 種硬幣能夠湊出金額 \(a\) 的最少硬幣數量,記為 \(dp[i, a]\) 。
二維 \(dp\) 表的尺寸為 \((n+1) \times (amt+1)\) 。
第二步:找出最優子結構,進而推導出狀態轉移方程
本題與完全背包問題的狀態轉移方程存在以下兩點差異。
- 本題要求最小值,因此需將運算子 \(\max()\) 更改為 \(\min()\) 。
- 最佳化主體是硬幣數量而非商品價值,因此在選中硬幣時執行 \(+1\) 即可。
第三步:確定邊界條件和狀態轉移順序
當目標金額為 \(0\) 時,湊出它的最少硬幣數量為 \(0\) ,即首列所有 \(dp[i, 0]\) 都等於 \(0\) 。
當無硬幣時,無法湊出任意 \(> 0\) 的目標金額,即是無效解。為使狀態轉移方程中的 \(\min()\) 函式能夠識別並過濾無效解,我們考慮使用 \(+ \infty\) 來表示它們,即令首行所有 \(dp[0, a]\) 都等於 \(+ \infty\) 。
2. 程式碼實現¶
大多數程式語言並未提供 \(+ \infty\) 變數,只能使用整型 int 的最大值來代替。而這又會導致大數越界:狀態轉移方程中的 \(+ 1\) 操作可能發生溢位。
為此,我們採用數字 \(amt + 1\) 來表示無效解,因為湊出 \(amt\) 的硬幣數量最多為 \(amt\) 。最後返回前,判斷 \(dp[n, amt]\) 是否等於 \(amt + 1\) ,若是則返回 \(-1\) ,代表無法湊出目標金額。程式碼如下所示:
def coin_change_dp(coins: list[int], amt: int) -> int:
"""零錢兌換:動態規劃"""
n = len(coins)
MAX = amt + 1
# 初始化 dp 表
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# 狀態轉移:首行首列
for a in range(1, amt + 1):
dp[0][a] = MAX
# 狀態轉移:其餘行和列
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
else:
# 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
return dp[n][amt] if dp[n][amt] != MAX else -1
/* 零錢兌換:動態規劃 */
int coinChangeDP(vector<int> &coins, int amt) {
int n = coins.size();
int MAX = amt + 1;
// 初始化 dp 表
vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
// 狀態轉移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 狀態轉移:其餘行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
/* 零錢兌換:動態規劃 */
int coinChangeDP(int[] coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
int[][] dp = new int[n + 1][amt + 1];
// 狀態轉移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 狀態轉移:其餘行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
/* 零錢兌換:動態規劃 */
int CoinChangeDP(int[] coins, int amt) {
int n = coins.Length;
int MAX = amt + 1;
// 初始化 dp 表
int[,] dp = new int[n + 1, amt + 1];
// 狀態轉移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0, a] = MAX;
}
// 狀態轉移:其餘行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i, a] = dp[i - 1, a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i, a] = Math.Min(dp[i - 1, a], dp[i, a - coins[i - 1]] + 1);
}
}
}
return dp[n, amt] != MAX ? dp[n, amt] : -1;
}
/* 零錢兌換:動態規劃 */
func coinChangeDP(coins []int, amt int) int {
n := len(coins)
max := amt + 1
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amt+1)
}
// 狀態轉移:首行首列
for a := 1; a <= amt; a++ {
dp[0][a] = max
}
// 狀態轉移:其餘行和列
for i := 1; i <= n; i++ {
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i-1][a]
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = int(math.Min(float64(dp[i-1][a]), float64(dp[i][a-coins[i-1]]+1)))
}
}
}
if dp[n][amt] != max {
return dp[n][amt]
}
return -1
}
/* 零錢兌換:動態規劃 */
func coinChangeDP(coins: [Int], amt: Int) -> Int {
let n = coins.count
let MAX = amt + 1
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
// 狀態轉移:首行首列
for a in 1 ... amt {
dp[0][a] = MAX
}
// 狀態轉移:其餘行和列
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1
}
/* 零錢兌換:動態規劃 */
function coinChangeDP(coins, amt) {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 狀態轉移:首行首列
for (let a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 狀態轉移:其餘行和列
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}
/* 零錢兌換:動態規劃 */
function coinChangeDP(coins: Array<number>, amt: number): number {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 狀態轉移:首行首列
for (let a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 狀態轉移:其餘行和列
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}
/* 零錢兌換:動態規劃 */
int coinChangeDP(List<int> coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
// 狀態轉移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 狀態轉移:其餘行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
/* 零錢兌換:動態規劃 */
fn coin_change_dp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
let max = amt + 1;
// 初始化 dp 表
let mut dp = vec![vec![0; amt + 1]; n + 1];
// 狀態轉移:首行首列
for a in 1..=amt {
dp[0][a] = max;
}
// 狀態轉移:其餘行和列
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = std::cmp::min(dp[i - 1][a], dp[i][a - coins[i - 1] as usize] + 1);
}
}
}
if dp[n][amt] != max {
return dp[n][amt] as i32;
} else {
-1
}
}
/* 零錢兌換:動態規劃 */
int coinChangeDP(int coins[], int amt, int coinsSize) {
int n = coinsSize;
int MAX = amt + 1;
// 初始化 dp 表
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(amt + 1, sizeof(int));
}
// 狀態轉移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 狀態轉移:其餘行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = myMin(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
int res = dp[n][amt] != MAX ? dp[n][amt] : -1;
// 釋放記憶體
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
/* 零錢兌換:動態規劃 */
fun coinChangeDP(coins: IntArray, amt: Int): Int {
val n = coins.size
val MAX = amt + 1
// 初始化 dp 表
val dp = Array(n + 1) { IntArray(amt + 1) }
// 狀態轉移:首行首列
for (a in 1..amt) {
dp[0][a] = MAX
}
// 狀態轉移:其餘行和列
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
}
}
}
return if (dp[n][amt] != MAX) dp[n][amt] else -1
}
### 零錢兌換:動態規劃 ###
def coin_change_dp(coins, amt)
n = coins.length
_MAX = amt + 1
# 初始化 dp 表
dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
# 狀態轉移:首行首列
(1...(amt + 1)).each { |a| dp[0][a] = _MAX }
# 狀態轉移:其餘行和列
for i in 1...(n + 1)
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
else
# 不選和選硬幣 i 這兩種方案的較小值
dp[i][a] = [dp[i - 1][a], dp[i][a - coins[i - 1]] + 1].min
end
end
end
dp[n][amt] != _MAX ? dp[n][amt] : -1
end
視覺化執行
圖 14-25 展示了零錢兌換的動態規劃過程,和完全背包問題非常相似。
圖 14-25 零錢兌換問題的動態規劃過程
圖解 14-25:零錢兌換的動態規劃
按硬幣種類與目標金額逐格填表,求恰好湊出 4 元所需的最少硬幣枚數。
可選硬幣面值為 1、2、5 元(共 3 種,每種均可重複選取),目標金額為 4 元。狀態 dp[i, a] 表示僅用前 i 種硬幣恰好湊出金額 a 的最少硬幣枚數;二維 dp 表共 4 行 5 列,行索引 i 從 0 至 3,列索引 a 從 0 至 4。
MAX = 目標金額 + 1 = 5 是表示“不可達(無解)”的邊界標記,絕非需要 5 枚硬幣。目標金額 0 不需要硬幣,首列邊界值為 0;無硬幣可用(i = 0)時,任何正金額均不可達。
先建立 4×5 全零表,再將首行正金額格 dp[0, 1] 至 dp[0, 4] 設為不可達標記 MAX = 5,首列 dp[0, 0] 至 dp[3, 0] 保持有效邊界 0。隨後按行 i = 1 至 3、每行金額 a = 1 至 4 依次填表:當前硬幣面值大於金額 a 時無法選入,直接繼承正上方 dp[i - 1, a];否則比較上方 dp[i - 1, a](不選該硬幣)與本行左方 dp[i, a - 面值] + 1(選入一枚該硬幣),取較小值。從本行左方轉移允許重複選取同種硬幣。
每步保留一張完整 dp 狀態表,表名含步號及本步動作,行頭同時給出 i 與可用面值,列頭給出金額。首列邊界格標為“邊界已設”,首行無解格標為“MAX,不可達邊界”;此前步驟寫入的格標為“已計算”;未計算格標為“未計算初值”,不能當作已求得的最少枚數。本步新算出的格標為“本步寫入”,最後一步將右下角標為“返回值”;可在第 15 步表中查詢全部最終值。
| 編號i | 面值 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
建立 4×5 初始全零 dp 表
根據 3 種硬幣(面值 1、2、5)與目標金額 4,建立 4×5 的二維 dp 表(行 i = 0 至 3,列 a = 0 至 4)。剛分配時所有單元格預設置為 0:首列金額 0 的 0 即為已設邊界(湊出 0 元需 0 枚硬幣),而其餘正金額格的 0 均為尚未計算的初值,等待下一步設定首行 MAX 不可達邊界。
零錢兌換第 1 步:建立全零表後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=1,面值 1 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=2,面值 1、2 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 設定首行正金額為不可達邊界 MAX = 5
無硬幣可用(i = 0)時無法湊出任何大於 0 的金額,因此將首行正金額格 dp[0, 1] 至 dp[0, 4] 設為不可達標記 MAX = 5(表示狀態已定義為無解,而非需要 5 枚硬幣);金額 a = 0 時最少需 0 枚硬幣,首列 dp[0, 0] 至 dp[3, 0] 保持已設邊界 0。第 1 至 3 行正金額格的 0 仍為未計算初值。
零錢兌換第 2 步:初始化邊界後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=2,面值 1、2 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[1, 1](面值 1、金額 1):最少 1 枚
開始處理第 1 種硬幣(面值 1),計算金額 a = 1 的 dp[1, 1]:不選面值 1 硬幣時取正上方 dp[0, 1] = MAX(5,不可達);選入 1 枚面值 1 硬幣時取本行左方邊界 dp[1, 0] = 0 加 1 得 1。取較小值 min(MAX, 1) = 1,寫入 dp[1, 1] = 1。這對應 1 枚 1 元硬幣。
零錢兌換第 3 步:計算 dp[1, 1]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,本步寫入 0,未計算初值 0,未計算初值 0,未計算初值 i=2,面值 1、2 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[1, 2](面值 1、金額 2):最少 2 枚
繼續用第 1 種硬幣(面值 1)計算金額 a = 2 的 dp[1, 2]:不選時為正上方 dp[0, 2] = MAX(不可達);選入 1 枚面值 1 硬幣時,複用本行左方剛算出的 dp[1, 1] = 1 再加 1 得 2(兩枚 1 元)。取 min(MAX, 2) = 2,寫入 dp[1, 2] = 2。
零錢兌換第 4 步:計算 dp[1, 2]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,本步寫入 0,未計算初值 0,未計算初值 i=2,面值 1、2 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[1, 3](面值 1、金額 3):最少 3 枚
繼續用第 1 種硬幣(面值 1)計算金額 a = 3 的 dp[1, 3]:不選時為正上方 dp[0, 3] = MAX(不可達);選入 1 枚面值 1 硬幣時由本行左方 dp[1, 2] = 2 加 1 得 3(三枚 1 元)。取 min(MAX, 3) = 3,寫入 dp[1, 3] = 3。
零錢兌換第 5 步:計算 dp[1, 3]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,本步寫入 0,未計算初值 i=2,面值 1、2 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[1, 4](面值 1、金額 4):最少 4 枚
繼續用第 1 種硬幣(面值 1)計算金額 a = 4 的 dp[1, 4]:不選時為正上方 dp[0, 4] = MAX(不可達);選入 1 枚面值 1 硬幣時由本行左方 dp[1, 3] = 3 加 1 得 4(四枚 1 元)。取 min(MAX, 4) = 4 寫入 dp[1, 4],第 1 行計算完畢。
零錢兌換第 6 步:計算 dp[1, 4]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,本步寫入 i=2,面值 1、2 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[2, 1](面值 2、金額 1):面值過大,繼承 1 枚
進入第 2 行,引入第 2 種硬幣(面值 2),計算金額 a = 1 的 dp[2, 1]。由於硬幣面值 2 大於當前金額 1,無法選入 2 元硬幣,直接繼承正上方 dp[1, 1] = 1,寫入 dp[2, 1] = 1。
零錢兌換第 7 步:計算 dp[2, 1]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,本步寫入 0,未計算初值 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[2, 2](面值 2、金額 2):選 1 枚 2 元,寫入 1
處理第 2 種硬幣(面值 2)、金額 a = 2:不選 2 元硬幣時繼承正上方 dp[1, 2] = 2(兩枚 1 元);選入 1 枚 2 元硬幣時從本行左方邊界 dp[2, 0] = 0 加 1 得 1(1 枚 2 元)。取較小值 min(2, 1) = 1,寫入 dp[2, 2] = 1。
零錢兌換第 8 步:計算 dp[2, 2]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,本步寫入 0,未計算初值 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[2, 3](面值 2、金額 3):1 元加 2 元,寫入 2 枚
處理第 2 種硬幣(面值 2)、金額 a = 3:不選 2 元硬幣時為正上方 dp[1, 3] = 3(三枚 1 元);選入 1 枚 2 元硬幣時從本行左方 dp[2, 1] = 1(1 枚 1 元)加 1 得 2(1 元與 2 元各 1 枚)。取 min(3, 2) = 2,寫入 dp[2, 3] = 2。
零錢兌換第 9 步:計算 dp[2, 3]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,本步寫入 0,未計算初值 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[2, 4](面值 2、金額 4):重複選 2 元,寫入 2 枚
處理第 2 種硬幣(面值 2)、金額 a = 4:不選 2 元硬幣時為正上方 dp[1, 4] = 4(四枚 1 元);選入 2 元硬幣時,從本行左方已更新的 dp[2, 2] = 1(已含 1 枚 2 元)再加 1 得 2(兩枚 2 元)。取 min(4, 2) = 2 寫入 dp[2, 4],完成第 2 行,體現本行左方轉移可重複選取同種硬幣。
零錢兌換第 10 步:計算 dp[2, 4]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,已計算 2,本步寫入 i=3,面值 1、2、5 0,邊界已設 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[3, 1](面值 5、金額 1):面值過大,繼承 1 枚
進入第 3 行,引入第 3 種硬幣(面值 5),計算金額 a = 1 的 dp[3, 1]。由於面值 5 大於當前金額 1,無法選入 5 元硬幣,直接繼承正上方 dp[2, 1] = 1,寫入 dp[3, 1] = 1。
零錢兌換第 11 步:計算 dp[3, 1]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,已計算 2,已計算 i=3,面值 1、2、5 0,邊界已設 1,本步寫入 0,未計算初值 0,未計算初值 0,未計算初值 計算 dp[3, 2](面值 5、金額 2):面值過大,繼承 1 枚
繼續處理第 3 種硬幣(面值 5)、金額 a = 2:面值 5 仍大於當前金額 2,無法選入 5 元硬幣,直接繼承正上方 dp[2, 2] = 1,寫入 dp[3, 2] = 1。
零錢兌換第 12 步:計算 dp[3, 2]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,已計算 2,已計算 i=3,面值 1、2、5 0,邊界已設 1,已計算 1,本步寫入 0,未計算初值 0,未計算初值 計算 dp[3, 3](面值 5、金額 3):面值過大,繼承 2 枚
繼續處理第 3 種硬幣(面值 5)、金額 a = 3:面值 5 大於當前金額 3,無法選入 5 元硬幣,直接繼承正上方 dp[2, 3] = 2,寫入 dp[3, 3] = 2。
零錢兌換第 13 步:計算 dp[3, 3]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,已計算 2,已計算 i=3,面值 1、2、5 0,邊界已設 1,已計算 1,已計算 2,本步寫入 0,未計算初值 計算 dp[3, 4](面值 5、金額 4):面值過大,繼承 2 枚
處理第 3 種硬幣(面值 5)、右下角目標金額 a = 4:由於面值 5 大於金額 4,無法選入 5 元硬幣,只能直接繼承正上方前兩種硬幣的解 dp[2, 4] = 2(即兩枚 2 元硬幣湊成 4 元),寫入 dp[3, 4] = 2,全表計算完成。
零錢兌換第 14 步:計算 dp[3, 4]後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,已計算 2,已計算 i=3,面值 1、2、5 0,邊界已設 1,已計算 1,已計算 2,已計算 2,本步寫入 讀取右下角 dp[3, 4],返回最少硬幣數 2
全部狀態轉移結束後,讀取右下角高亮格 dp[3, 4] = 2。由於該值不等於不可達標記 MAX(5),直接返回 2 作為恰好湊出 4 元的最少硬幣枚數(由兩枚 2 元硬幣組成;若結果為 MAX 則返回 -1)。本步不再改寫任何數值。
零錢兌換第 15 步:返回結果後的完整 dp 表(MAX=5,不可達) 前 i 種硬幣及可用面值 金額0 金額1 金額2 金額3 金額4 i=0,無硬幣 0,邊界已設 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 MAX,不可達邊界 i=1,面值 1 0,邊界已設 1,已計算 2,已計算 3,已計算 4,已計算 i=2,面值 1、2 0,邊界已設 1,已計算 1,已計算 2,已計算 2,已計算 i=3,面值 1、2、5 0,邊界已設 1,已計算 1,已計算 2,已計算 2,返回值
面值 5 大於本表各正金額 1 至 4,因此第 3 行繼承前兩種硬幣的結果。程式碼在最終值為 MAX 時返回 -1,表示無解。
3. 空間最佳化¶
零錢兌換的空間最佳化的處理方式和完全背包問題一致:
def coin_change_dp_comp(coins: list[int], amt: int) -> int:
"""零錢兌換:空間最佳化後的動態規劃"""
n = len(coins)
MAX = amt + 1
# 初始化 dp 表
dp = [MAX] * (amt + 1)
dp[0] = 0
# 狀態轉移
for i in range(1, n + 1):
# 正序走訪
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
else:
# 不選和選硬幣 i 這兩種方案的較小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
return dp[amt] if dp[amt] != MAX else -1
/* 零錢兌換:空間最佳化後的動態規劃 */
int coinChangeDPComp(vector<int> &coins, int amt) {
int n = coins.size();
int MAX = amt + 1;
// 初始化 dp 表
vector<int> dp(amt + 1, MAX);
dp[0] = 0;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零錢兌換:空間最佳化後的動態規劃 */
int coinChangeDPComp(int[] coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
int[] dp = new int[amt + 1];
Arrays.fill(dp, MAX);
dp[0] = 0;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零錢兌換:空間最佳化後的動態規劃 */
int CoinChangeDPComp(int[] coins, int amt) {
int n = coins.Length;
int MAX = amt + 1;
// 初始化 dp 表
int[] dp = new int[amt + 1];
Array.Fill(dp, MAX);
dp[0] = 0;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = Math.Min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零錢兌換:動態規劃 */
func coinChangeDPComp(coins []int, amt int) int {
n := len(coins)
max := amt + 1
// 初始化 dp 表
dp := make([]int, amt+1)
for i := 1; i <= amt; i++ {
dp[i] = max
}
// 狀態轉移
for i := 1; i <= n; i++ {
// 正序走訪
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = int(math.Min(float64(dp[a]), float64(dp[a-coins[i-1]]+1)))
}
}
}
if dp[amt] != max {
return dp[amt]
}
return -1
}
/* 零錢兌換:空間最佳化後的動態規劃 */
func coinChangeDPComp(coins: [Int], amt: Int) -> Int {
let n = coins.count
let MAX = amt + 1
// 初始化 dp 表
var dp = Array(repeating: MAX, count: amt + 1)
dp[0] = 0
// 狀態轉移
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
}
}
}
return dp[amt] != MAX ? dp[amt] : -1
}
/* 零錢兌換:空間最佳化後的動態規劃 */
function coinChangeDPComp(coins, amt) {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => MAX);
dp[0] = 0;
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] !== MAX ? dp[amt] : -1;
}
/* 零錢兌換:空間最佳化後的動態規劃 */
function coinChangeDPComp(coins: Array<number>, amt: number): number {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => MAX);
dp[0] = 0;
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] !== MAX ? dp[amt] : -1;
}
/* 零錢兌換:空間最佳化後的動態規劃 */
int coinChangeDPComp(List<int> coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
List<int> dp = List.filled(amt + 1, MAX);
dp[0] = 0;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零錢兌換:空間最佳化後的動態規劃 */
fn coin_change_dp_comp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
let max = amt + 1;
// 初始化 dp 表
let mut dp = vec![0; amt + 1];
dp.fill(max);
dp[0] = 0;
// 狀態轉移
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = std::cmp::min(dp[a], dp[a - coins[i - 1] as usize] + 1);
}
}
}
if dp[amt] != max {
return dp[amt] as i32;
} else {
-1
}
}
/* 零錢兌換:空間最佳化後的動態規劃 */
int coinChangeDPComp(int coins[], int amt, int coinsSize) {
int n = coinsSize;
int MAX = amt + 1;
// 初始化 dp 表
int *dp = malloc((amt + 1) * sizeof(int));
for (int j = 1; j <= amt; j++) {
dp[j] = MAX;
}
dp[0] = 0;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = myMin(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
int res = dp[amt] != MAX ? dp[amt] : -1;
// 釋放記憶體
free(dp);
return res;
}
/* 零錢兌換:空間最佳化後的動態規劃 */
fun coinChangeDPComp(coins: IntArray, amt: Int): Int {
val n = coins.size
val MAX = amt + 1
// 初始化 dp 表
val dp = IntArray(amt + 1)
dp.fill(MAX)
dp[0] = 0
// 狀態轉移
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
} else {
// 不選和選硬幣 i 這兩種方案的較小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
}
}
}
return if (dp[amt] != MAX) dp[amt] else -1
}
### 零錢兌換:空間最佳化後的動態規劃 ###
def coin_change_dp_comp(coins, amt)
n = coins.length
_MAX = amt + 1
# 初始化 dp 表
dp = Array.new(amt + 1, _MAX)
dp[0] = 0
# 狀態轉移
for i in 1...(n + 1)
# 正序走訪
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
else
# 不選和選硬幣 i 這兩種方案的較小值
dp[a] = [dp[a], dp[a - coins[i - 1]] + 1].min
end
end
end
dp[amt] != _MAX ? dp[amt] : -1
end
視覺化執行
14.5.3 零錢兌換問題 II¶
Question
給定 \(n\) 種硬幣,第 \(i\) 種硬幣的面值為 \(coins[i - 1]\) ,目標金額為 \(amt\) ,每種硬幣可以重複選取,問湊出目標金額的硬幣組合數量。示例如圖 14-26 所示。
圖 14-26 零錢兌換問題 II 的示例資料
圖解 14-26:零錢兌換 II 的硬幣組合數
使用可重複選取的面值 1、2、5 硬幣恰好湊出目標金額 5,不計取幣順序時共有 4 種不同組合。
零錢兌換問題 II 同樣給定面值為 [1, 2, 5] 的 3 種無限量硬幣,但本示例的目標金額設為 amt = 5,且求解目標不再是“最少硬幣枚數”,而是統計“恰好湊出目標金額 5 的硬幣組合數量”(只改變硬幣排列順序而各面值枚數相同的方案視為同一種組合)。
左上方的硬幣表透過向右的粗灰色箭頭指向標有“目標金額 amt = 5”的錢袋。下半部分結果框列出“硬幣組合數量:4”,並在“硬幣組合方案:”右側逐行畫出四個硬幣加法算式。
下方第一張表列出輸入面值,第二張表按圖中算式的順序列出全部組合。各面值的枚數是對算式中硬幣個數的統計,原圖未另畫這張計數表。
| 編號i | 面值 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 方案 | 面值1數量 | 面值2數量 | 面值5數量 |
|---|---|---|---|
| 1+1+1+1+1 | 5 | 0 | 0 |
| 1+1+1+2 | 3 | 1 | 0 |
| 1+2+2 | 1 | 2 | 0 |
| 5 | 0 | 0 | 1 |
根據輸入補充分類驗證:若用面值 5,只能單取 1 枚;若不用面值 5,則面值 2 只能取 2、1、0 枚,分別用 1、3、5 枚面值 1 補足。這樣恰有表中的四種無序組合,沒有遺漏。
1. 動態規劃思路¶
相比於上一題,本題目標是求組合數量,因此子問題變為:前 \(i\) 種硬幣能夠湊出金額 \(a\) 的組合數量。而 \(dp\) 表仍然是尺寸為 \((n+1) \times (amt + 1)\) 的二維矩陣。
當前狀態的組合數量等於不選當前硬幣與選當前硬幣這兩種決策的組合數量之和。狀態轉移方程為:
當目標金額為 \(0\) 時,無須選擇任何硬幣即可湊出目標金額,因此應將首列所有 \(dp[i, 0]\) 都初始化為 \(1\) 。當無硬幣時,無法湊出任何 \(>0\) 的目標金額,因此首行所有 \(dp[0, a]\) 都等於 \(0\) 。
2. 程式碼實現¶
def coin_change_ii_dp(coins: list[int], amt: int) -> int:
"""零錢兌換 II:動態規劃"""
n = len(coins)
# 初始化 dp 表
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# 初始化首列
for i in range(n + 1):
dp[i][0] = 1
# 狀態轉移
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
else:
# 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
return dp[n][amt]
/* 零錢兌換 II:動態規劃 */
int coinChangeIIDP(vector<int> &coins, int amt) {
int n = coins.size();
// 初始化 dp 表
vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零錢兌換 II:動態規劃 */
int coinChangeIIDP(int[] coins, int amt) {
int n = coins.length;
// 初始化 dp 表
int[][] dp = new int[n + 1][amt + 1];
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零錢兌換 II:動態規劃 */
int CoinChangeIIDP(int[] coins, int amt) {
int n = coins.Length;
// 初始化 dp 表
int[,] dp = new int[n + 1, amt + 1];
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i, 0] = 1;
}
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i, a] = dp[i - 1, a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i, a] = dp[i - 1, a] + dp[i, a - coins[i - 1]];
}
}
}
return dp[n, amt];
}
/* 零錢兌換 II:動態規劃 */
func coinChangeIIDP(coins []int, amt int) int {
n := len(coins)
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amt+1)
}
// 初始化首列
for i := 0; i <= n; i++ {
dp[i][0] = 1
}
// 狀態轉移:其餘行和列
for i := 1; i <= n; i++ {
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i-1][a]
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]
}
}
}
return dp[n][amt]
}
/* 零錢兌換 II:動態規劃 */
func coinChangeIIDP(coins: [Int], amt: Int) -> Int {
let n = coins.count
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
// 初始化首列
for i in 0 ... n {
dp[i][0] = 1
}
// 狀態轉移
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
}
}
}
return dp[n][amt]
}
/* 零錢兌換 II:動態規劃 */
function coinChangeIIDP(coins, amt) {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 初始化首列
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零錢兌換 II:動態規劃 */
function coinChangeIIDP(coins: Array<number>, amt: number): number {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 初始化首列
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零錢兌換 II:動態規劃 */
int coinChangeIIDP(List<int> coins, int amt) {
int n = coins.length;
// 初始化 dp 表
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零錢兌換 II:動態規劃 */
fn coin_change_ii_dp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
// 初始化 dp 表
let mut dp = vec![vec![0; amt + 1]; n + 1];
// 初始化首列
for i in 0..=n {
dp[i][0] = 1;
}
// 狀態轉移
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1] as usize];
}
}
}
dp[n][amt]
}
/* 零錢兌換 II:動態規劃 */
int coinChangeIIDP(int coins[], int amt, int coinsSize) {
int n = coinsSize;
// 初始化 dp 表
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(amt + 1, sizeof(int));
}
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
int res = dp[n][amt];
// 釋放記憶體
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
/* 零錢兌換 II:動態規劃 */
fun coinChangeIIDP(coins: IntArray, amt: Int): Int {
val n = coins.size
// 初始化 dp 表
val dp = Array(n + 1) { IntArray(amt + 1) }
// 初始化首列
for (i in 0..n) {
dp[i][0] = 1
}
// 狀態轉移
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
}
}
}
return dp[n][amt]
}
### 零錢兌換 II:動態規劃 ###
def coin_change_ii_dp(coins, amt)
n = coins.length
# 初始化 dp 表
dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
# 初始化首列
(0...(n + 1)).each { |i| dp[i][0] = 1 }
# 狀態轉移
for i in 1...(n + 1)
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超過目標金額,則不選硬幣 i
dp[i][a] = dp[i - 1][a]
else
# 不選和選硬幣 i 這兩種方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
end
end
end
dp[n][amt]
end
視覺化執行
3. 空間最佳化¶
空間最佳化處理方式相同,刪除硬幣維度即可:
def coin_change_ii_dp_comp(coins: list[int], amt: int) -> int:
"""零錢兌換 II:空間最佳化後的動態規劃"""
n = len(coins)
# 初始化 dp 表
dp = [0] * (amt + 1)
dp[0] = 1
# 狀態轉移
for i in range(1, n + 1):
# 正序走訪
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
else:
# 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
return dp[amt]
/* 零錢兌換 II:空間最佳化後的動態規劃 */
int coinChangeIIDPComp(vector<int> &coins, int amt) {
int n = coins.size();
// 初始化 dp 表
vector<int> dp(amt + 1, 0);
dp[0] = 1;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
int coinChangeIIDPComp(int[] coins, int amt) {
int n = coins.length;
// 初始化 dp 表
int[] dp = new int[amt + 1];
dp[0] = 1;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
int CoinChangeIIDPComp(int[] coins, int amt) {
int n = coins.Length;
// 初始化 dp 表
int[] dp = new int[amt + 1];
dp[0] = 1;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
func coinChangeIIDPComp(coins []int, amt int) int {
n := len(coins)
// 初始化 dp 表
dp := make([]int, amt+1)
dp[0] = 1
// 狀態轉移
for i := 1; i <= n; i++ {
// 正序走訪
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a-coins[i-1]]
}
}
}
return dp[amt]
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
func coinChangeIIDPComp(coins: [Int], amt: Int) -> Int {
let n = coins.count
// 初始化 dp 表
var dp = Array(repeating: 0, count: amt + 1)
dp[0] = 1
// 狀態轉移
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
}
}
}
return dp[amt]
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
function coinChangeIIDPComp(coins, amt) {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => 0);
dp[0] = 1;
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
function coinChangeIIDPComp(coins: Array<number>, amt: number): number {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => 0);
dp[0] = 1;
// 狀態轉移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
int coinChangeIIDPComp(List<int> coins, int amt) {
int n = coins.length;
// 初始化 dp 表
List<int> dp = List.filled(amt + 1, 0);
dp[0] = 1;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
fn coin_change_ii_dp_comp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
// 初始化 dp 表
let mut dp = vec![0; amt + 1];
dp[0] = 1;
// 狀態轉移
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1] as usize];
}
}
}
dp[amt]
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
int coinChangeIIDPComp(int coins[], int amt, int coinsSize) {
int n = coinsSize;
// 初始化 dp 表
int *dp = calloc(amt + 1, sizeof(int));
dp[0] = 1;
// 狀態轉移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a];
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
int res = dp[amt];
// 釋放記憶體
free(dp);
return res;
}
/* 零錢兌換 II:空間最佳化後的動態規劃 */
fun coinChangeIIDPComp(coins: IntArray, amt: Int): Int {
val n = coins.size
// 初始化 dp 表
val dp = IntArray(amt + 1)
dp[0] = 1
// 狀態轉移
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
} else {
// 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
}
}
}
return dp[amt]
}
### 零錢兌換 II:空間最佳化後的動態規劃 ###
def coin_change_ii_dp_comp(coins, amt)
n = coins.length
# 初始化 dp 表
dp = Array.new(amt + 1, 0)
dp[0] = 1
# 狀態轉移
for i in 1...(n + 1)
# 正序走訪
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超過目標金額,則不選硬幣 i
dp[a] = dp[a]
else
# 不選和選硬幣 i 這兩種方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
end
end
end
dp[amt]
end