裝貨物
- 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; }
