题意:
有 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; }