問題描述
兩輛車載重 C1, C2 (≤100)，n ≤ 10 件傢俱重量 w_i。每次搬運可將部分傢俱分載兩車 (各不超載)，求最少搬運次數運完所有傢俱。
解法：狀態壓縮預處理 + 背包 DP
- 枚舉所有子集 (共
2^n ≤ 1024)，判斷該子集能否一次搬完：即能否分成兩組，重量分別 ≤ C1 和 ≤ C2。用 01 背包在子集內求可行裝載：dp[v] 表示車1能否裝載重量 v，若存在 v ≤ C1 且 sum - v ≤ C2 則可行。
- 集合覆蓋 DP：
f[mask] = 覆蓋狀態 mask 所需最少次數。初始 f[0]=0，其餘 INF。對每個可行子集 s，轉移 f[mask | s] = min(f[mask | s], f[mask] + 1)。答案 f[(1<。
代碼實現
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
bool can_take(int mask, const vector& w, int C1, int C2) {
int sum = 0;
vector items;
for (int i = 0; i < w.size(); ++i)
if (mask & (1< C1 + C2) return false;
vector dp(C1+1, false);
dp[0] = true;
for (int wt : items)
for (int v = C1; v >= wt; --v)
if (dp[v-wt]) dp[v] = true;
for (int v = 0; v <= C1; ++v)
if (dp[v] && sum - v <= C2) return true;
return false;
}
int main() {
int T; cin >> T;
for (int tc = 1; tc <= T; ++tc) {
int n, C1, C2; cin >> n >> C1 >> C2;
vector w(n);
for (int &x : w) cin >> x;
int ALL = (1< valid;
for (int mask = 1; mask <= ALL; ++mask)
if (can_take(mask, w, C1, C2)) valid.push_back(mask);
vector f(1<= 0; --mask)
if (f[mask] != INF)
f[mask | s] = min(f[mask | s], f[mask] + 1);
cout << "Scenario #" << tc << ":\n" << f[ALL] << "\n\n";
}
return 0;
}
複雜度
- 預處理：
2^n * n * C1 ≈ 1024 * 10 * 100 = 1e6。
- DP：
|valid| * 2^n，|valid| ≤ 1024，約 1e6。
- 總體極快。
總結
「狀態壓縮枚舉可行子集 + 集合覆蓋背包」是小 n 組合優化的標準模式。先判斷每個子集是否可行，再用背包 DP 求最少覆蓋次數。
