Change-Making Problem

2021-06-27 16:48:53 +0800 CST Tags: change-making, knapsack

問題：給定一個容量 $V$ 的箱子以及 $N$ 種體積分別為 v[i] 的物品 i，每種物品都無限量供應，請問最少用幾個物品就能把箱子填滿？

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

效能：空間複雜度 $\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
13

int n, V; // n := 物品數量、V := 箱子容量
int dp[V+1]; // dp[v] := 物品 1 ~ i 之中我們能選滿總體積為 v 的最少物品個數

memset(dp, 0x7f, sizeof dp); dp[0] = 1;
while (n--) {
    int v; cin >> v; // 輸入每個物品的體積
    for (int i=v; i<=V; i++) // 由小到大的順序才能 in-place 更新
        if (dp[i-v] + 1 < dp[i])
            dp[i] = dp[i-v] + 1;
}

// 詢問裝滿箱子所需要的最少物品數
cout << dp[V] << '\n';