有 n 件货物, 第 i 件重 Wi 吨,另有 x 个集装箱,每个集装箱可以装重量不超过 W 吨的货物。
货物不能分拆,请判断这 x 个集装箱能否装下所有货物。
第一行一个整数 T ,表示数据组数。对于每组数据:第一行三个整数 n,x,W。第二行 n 个整数,第 i 个表示 Wi。
保证 1≤T≤
,1≤n≤21,1≤x,Wi
,W≤
, n>10的数据不会超过 2 组。
对于每组数据输出一行一个字符串,能装下所有货物输出 Yes ,否则输出 No 。
2
5 2 20
2 4 6 8 10
1 114514 1919810
114514
Yes
Yes
样例数据的一种可能方案:{4,6}, {2,8,10} 。
题目链接:https://ac.nowcoder.com/acm/contest/3781/C
自闭ing,我一开始以为这题是用贪心算法:总共x个集装箱 先把货物往第一个集装箱装,能装下就继续放下一个货物,不能装下就看第二 三... x个集装箱能不能,要是n件货物能全部装下就输出Yes否则输出No。 一提交直接WA,正确的思路应该是深度优先遍历+回溯法。先把所有的货物根据重量降序排列,然后从第一个货物开始用dfs,遍历u个集装箱看哪个箱子能放下当前货物(u为当前正在装载的货物个数),当集装箱能放下该货物时就开始遍历下一个货物,直到装载完n个货物为止return true输出Yes,否则输出No。
#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int maxn = 101;
int n,x,W; //货物数n,集装箱个数x,集装箱最多载重W
int w[maxn]; //w[i]表示第i件货物的重量
int box[maxn]; //box[i]表示第i集装箱当前装载的重量
bool dfs(int u) //u表示当前在装载第u个货物
{
if(u > n) return true;
for(int i = 1; i<=u && i<=x; i++) //看往哪个集装箱装,一定要i<=u不然会超时
{
if(box[i]+w[u] <= W)
{
box[i] += w[u];
if(dfs(u+1)) return true;
box[i] -= w[u];
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--)
{
cin >> n >> x >> W;
ms(w,0),ms(box,0); //初始化
Up(i,1,n)
{
cin >> w[i];
}
sort(w+1,w+1+n,greater<int>()); //降序排列
cout << (dfs(1) ? "Yes" : "No") << endl;
}
return 0;
}