装货物

根据数据量使用DFS暴力搜索。

对每个货物，我们可以进行两种操作：

1. 将其放入一个已有货物的箱子里（如果能放下）；
2. 放入一个空箱子里；

剪枝优化：

1. 对货物递减排序，先放大的货物可以减少操作一的次数；

参考代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define it insert
#define pob pop_back
#define pub push_back
#define emb emplace_back
#define all(v) (v).begin(), (v).end()
#define mkp(a, b) make_pair(a, b)
using LL = long long;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
const double EPS = 1e-6;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

int n, x, W;
int s[N], w[N];
int ans;

void dfs(int idx, int r) {
    if (r >= ans || r > x) return;
    if (idx >= n + 1) {
        ans = min(ans, r);
        return;
    }
    for (int i = 1; i <= r; ++i) {
        if (w[idx] + s[i] <= W) {
            s[i] += w[idx];
            dfs(idx + 1, r);
            s[i] -= w[idx];
        }
    }
    s[r + 1] = w[idx];
    dfs(idx + 1, r + 1);
    s[r + 1] = 0;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &x, &W);
        int flag = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            if (w[i] > W) flag = 1;
        }
        if (flag) {
            puts("No");
            continue;
        }
        sort(w + 1, w + n + 1, greater<int>());
        memset(s, 0, sizeof s);
        ans = INF;
        dfs(1, 1);
        if (ans <= x) puts("Yes");
        else puts("No");
    }
    return 0;
}

简化

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define it insert
#define pob pop_back
#define pub push_back
#define emb emplace_back
#define all(v) (v).begin(), (v).end()
#define mkp(a, b) make_pair(a, b)
using LL = long long;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
const double EPS = 1e-6;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

int n, x, W;
int s[N], w[N];

bool dfs(int idx) {
    if (idx >= n + 1) return 1;
    for (int i = 1; i <= min(idx + 1, x); ++i) {
        if (s[i] + w[idx] <= W) {
            s[i] += w[idx];
            if (dfs(idx + 1)) return 1;
            s[i] -= w[idx];
        }
    }
    return 0;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &x, &W);
        int flag = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            if (w[i] > W) flag = 1;
        }
        if (flag) {
            puts("No");
            continue;
        }
        sort(w + 1, w + n + 1, greater<>());
        memset(s, 0, sizeof s);
        if (dfs(0)) puts("Yes");
        else puts("No");
    }
    return 0;
}