子集合問題

2021-06-26 20:42:03 +0800 CST Tags: knapsack, subset-sum

問題：給定一個容量 $V$ 的箱子以及 $N$ 個體積分別為 v[i] 的物品 i，請問要怎麼把這些物品在容量限制內塞進箱子內才能使得箱子內的剩餘空間最小？另外再問有沒有辦法裝滿整個箱子呢？

解法：此乃 0/1 背包問題的應用，只要讓每個物品的價值就剛好等於它們各自的體積，就能套用背包問題的模型了。另外對於第二個問題因為只是要知道 YES 或 NO，原先的模型其實還可以更進一步修改為 dp$_i[v] = $ dp$_{i-1}[v]\ \lor$ dp$_{i-1}\big[v\ -$ v$[i]\big]$，子問題 dp$_i[v]$ 的意思是當候選物品為 1 到 $i$ 的時候，是否可能讓背包內的物品總體積剛好為 $v$，那麼易知本題答案為 dp$_N[V]$。記得一開始要 dp$_0[0]$ = true。

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

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

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

// 詢問可否裝滿箱子
cout << dp[V] << '\n';