【每日一题】装货物 题解

Description

有 n 件货物， 第 i 件重 吨，另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。
货物不能分拆，请判断这 x 个集装箱能否装下所有货物。

Solution

, 考虑搜索，由于货物不能拆分，于是我们所需要的集装箱最多需要 个，那么我们可以预处理出 个容量为 的桶，然后每次搜索能否放到该桶里面，最后回溯。
注意这道题还需要一些剪枝技巧，详情看代码。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 23 + 5;
int a[N], table[N], n, x, w;
bool flag;
void dfs(int now) {
    if(flag) return ;
    if(now == n + 1) {
        flag = 1; return ;
    }
    int in = 0;
    for(int i = 1; i <= min(now, x); i++) { // 如果是min(now,x)会TLE
        if(table[i] >= a[now]) {
            table[i] -= a[now];
            dfs(now + 1);
            if(flag) return ;
            table[i] += a[now];
            in = 1;
        }
    }
    if(!in) return ;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while(T--) {
        cin >> n >> x >> w;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n, greater<int>());
        flag = false;
        for(int i = 1; i <= n; i++) table[i] = w;
        dfs(1);
        if(flag) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}