💡 题解分析

🚩 本质问题：

将 $n$ 件家具划分为若干组，每一组可在一次运输中由两辆车共同装走，目标是使得组数最少。

🧠 解题思路：

✅ 1. 穷举所有划分方案（状态压缩） $n \leq 10$，最多 $2^{10} = 1024$ 个子集，可以穷举每种搬运组合。

用状态压缩（mask）表示哪些家具已经搬运。

对每个状态，尝试找一组能一次搬完的组合（合法的子集），然后转移到剩下未搬的部分。

最终求出完成搬运的所有状态中，需要的最少次数。

✅ 2. 判断某一组是否能被两辆车一次搬完 判断某个家具集合 $S$ 是否可以划分成两个子集 $A$ 和 $B$，满足：

∑ 𝑖 ∈ 𝐴 𝑤 𝑖 ≤ 𝐶 1 且 ∑ 𝑖 ∈ 𝐵 𝑤 𝑖 ≤ 𝐶 2 i∈A ∑ ​ w i ​ ≤C 1 ​ 且 i∈B ∑ ​ w i ​ ≤C 2 ​

这可以转化为0-1 背包问题：从 $S$ 中选若干件家具装入车1（容量 $C_1$），其余给车2。

✅ 3. 使用记忆化搜索或动态规划优化 使用 dp[mask] 表示处理完集合 mask 中家具所需的最少次数。

初始：dp[0] = 0，表示无家具时0次

对于每个状态 mask，枚举所有合法子集 submask，如果 submask 是一次可运输的集合：

更新 dp[mask | submask] = min(dp[mask | submask], dp[mask] + 1)

⏱ 时间复杂度分析

枚举状态数：$2^n = 1024$

每个状态内判断是否能被两辆车装走：一个 0-1 背包 $O(n \cdot C_1)$

所以总复杂度：$O(2^n \cdot n \cdot C_1)$，完全可以接受 ✅

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, C1, C2;
const int maxn = 1<<12;
const int INF = 0x3f3f3f3f;
int a[12], ok[maxn], dp[maxn];

bool judge(int state){
    int val[105];
    memset(val, 0, sizeof(val));
    val[0] = 1;
    int sum = 0, sum1 = 0;
    for(int i = 0; i < n; i++){
        if(state & (1<<i)){
            sum += a[i];
            for(int j = C1; j >= 0; j--)
                if(j - a[i] >= 0 && val[j-a[i]]) val[j] = 1;
        }
    }
    for(int j = C1; j >= 0; j--) if(val[j]) {sum1 = j; break;}
    if(sum - sum1 > C2) return false;
    return true;
}

int main(){
    int T;
    scanf("%d", &T);
    for(int kase = 1; kase <= T; kase++){
        scanf("%d%d%d", &n, &C1, &C2);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        int cnt = 0;
        for(int i = 0; i < (1<<n); i++){
            dp[i] = INF;
            if(judge(i)) ok[cnt++] = i;
        }
        dp[0] = 0;
        for(int i = 0; i < (1<<n); i++)
            for(int j = 0; j < cnt; j++)
                dp[i|ok[j]] = min(dp[i|ok[j]], dp[i]+1);
        printf("Scenario #%d:\n%d\n\n", kase, dp[(1<<n)-1]);
    }
    return 0;
}