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