题目

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

解题思路

  • 先确定最重的货物重量 ，如果 ，因为货物不能分拆，所以这些集装箱不能装下这个货物。

  • 再比较 和 ，如果 ，那么每个货物都可以单独放置一个集装箱，所以答案是 Yes。

  • 如果 ，使用回溯算法。

表示第 个集装箱当前装下货物的重量。

回溯算法：
试着将第 个货物放到第 个集装箱中，如果可以装下，就装进去，，然后装第 个货物。
如果装完了所有货物，就返回 true。
如果上述方案失败，就返回前一步，重置成之前的状态，，将第 个货物放到第 个集装箱中。重复上述步骤。
如果试完了所有集装箱，而货物还没装完，返回 false。

装第 个货物时，可以只考虑前 个箱子，假如使用了 个箱子，至少会出现一个空箱子。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> w, a;
int n, x, W;

bool dfs(int k){
    if(k==n)
        return true;
    for(int i=0; i<min(k+1,x); ++i){
        if(a[i]+w[k]<=W){
            a[i]+=w[k];
            if(dfs(k+1))
                return true;
            a[i]-=w[k];
        }
    }
    return false;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n >> x >> W;
        w.resize(n);
        int ma = 0;
        for(int i=0; i<n; ++i){
            cin >> w[i];
            ma = max(ma, w[i]);
        }
        if(ma>W){
            cout << "No" << endl;
            continue;
        }
        if(n<=x){
            cout << "Yes" << endl;
            continue;
        }

        a.resize(x,0);
        for(int i=0; i<x; ++i) a[i]=0;

        if(dfs(0))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}