题解 | #装货物#

有 n 件货物， 第i件重$w_{i}w\_i$吨，另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。 货物不能分拆，请判断这 x 个集装箱能否装下所有货物。
n的数据很小，所以可以考虑爆搜
AC代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
const ll mod = 1e9 + 7;
long long n, x, W, w[25], b[25];
int dfs(int now)
{
    //如果上一个状态已经装满之后，返回true
    if (now == n + 1)
        return 1;
    for (int i = 1; i <= min(x, now); i++)
    {
        /*now实际上就像同时开了一个新的盒子和一个新的物体
        如果前面盒子放的下，就放入
        不能就放入新开的盒子中
        如果都不能放入，则返回false
        */
        if (b[i] + w[now] > W)
            continue;
        //如果这个盒子可以装下，我们用这个盒子装下之后的状态遍历下一个状态
        b[i] += w[now];
        if (dfs(now + 1))
            return 1;
        //不装入这个盒子，改判其他盒子
        b[i] -= w[now];
    }
    return 0;
}
void dilingtian()
{
    cin >> n >> x >> W;
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    if (dfs(1))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        dilingtian();
    return 0;
}