装货物
- 2020 年 2 月 13 日
- 筆記
题目描述：
有 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。
AC代码：
#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; }
