题意:
有 n 件货物, 第 i 件重 wiw_iwi​ 吨,另有 x 个集装箱,每个集装箱可以装重量不超过 W 吨的货物。
货物不能分拆,请判断这 x 个集装箱能否装下所有货物。
题解:
这题一开始TLE,无奈,看了dalao们的解法,感觉这题主要还是考这一个剪枝吧,在考虑要把这个货物装到哪个箱子的时候,对于每一个货物,我们单独给他开一个空箱子,如果是多个的话,那并没有什么意义,会有特别多的重复情况,(放到哪个空箱子不是放)。

for(int i=1;i<=min(steps,x);i++)

代码:

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <cctype>
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 100;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
using namespace std;
int a[maxn];
int box[maxn];
bool flag=false;
int n,x,w;

void dfs(int steps){
    if(steps==n+1){
        flag=true;
        return;
    }
    if(flag) return;
    for(int i=1;i<=min(steps,x);i++){
        if(box[i]+a[steps]>w) continue;
        box[i]+=a[steps];
        dfs(steps+1);
        box[i]-=a[steps];
    }
    return ;
}

signed main()
{
    int t;
    cin>>t;
    while(t--){
        flag=false;
        cin>>n>>x>>w;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1,greater<int>());
        dfs(1);
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}