Coin Change Problem

2021-06-27 12:53:03 +0800 CST Tags: coin-change, combinatorics, knapsack

問題：給定一個容量 $V$ 的箱子以及 $N$ 種體積分別為 v[i] 的物品 i，每種物品都無限量供應，那麼只用這幾種物品就能把箱子填滿的方法數總共有幾種？

解法：此乃 0/1 背包問題的變形，算法也和原本的模型非常相似。其實只是排列組合的「加法原理」的實現而已，考慮子問題 dp$_i[v]$ 為當候選物品為 1 到 $i$ 的時候能湊成體積 $v$ 的方法數，那麼易知本題答案為 dp$_N[V]$。其遞迴式為 dp$_i[v] = $ dp$_{i-1}[v]\ +$ dp$_i\big[v\ -$ v$[i]\big]$，它的意思是說當我在體積 $v$ 的時候如果都不選物品 i，那這個 case 的方法數剛好就是只考慮物品 1 到 $i-1$ 的時候同體積的方法數；如果已經確定至少選了一個物品 i，那麼這個 case 的方法數剛好就是仍然考慮物品 1 到 $i$ 的時候排除一個物品 i 體積的方法數；把這兩個 cases 的方法數加起來就是原本子問題的答案了。另外在更新一個完整回合的 dp 的時候和原本的背包問題一樣都有一個固定的順序，就是由於一個體積的更新會用到當下這個回合較小的體積，所以必須由小到大才能 in-place 更新，才能確保任意時刻 dp 的較小部分屬第 $i$ 回合，較大部分屬第 $i-1$ 回合而不相衝。最後記得一開始要 dp$_0[0]$ = 1。

效能：空間複雜度 $\mathcal O(V)$、時間複雜度 $\mathcal O(NV)$。

附註：
[1] https://web.ntnu.edu.tw/~algo/KnapsackProblem.html#6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int n, V; // n := 物品數量、V := 箱子容量
int dp[V+1]; // dp[v] := 物品 1 ~ i 之中我們能選滿總體積為 v 的方法數
             // 一開始須歸零
dp[0] = 1;
while (n--) {
    int v; cin >> v; // 輸入每個物品的體積
    for (int i=v; i<=V; i++) // 由小到大的順序才能 in-place 更新
        dp[i] += dp[i-v];
}

// 詢問裝滿箱子的方法數
cout << dp[V] << '\n';