[装货物](https://ac.nowcoder.com/acm/problem/200532)
装货物
https://ac.nowcoder.com/acm/problem/200532
装货物
根据数据量使用DFS暴力搜索。
对每个货物,我们可以进行两种操作:
- 将其放入一个已有货物的箱子里(如果能放下);
- 放入一个空箱子里;
剪枝优化:
- 对货物递减排序,先放大的货物可以减少操作一的次数;
参考代码
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define it insert #define pob pop_back #define pub push_back #define emb emplace_back #define all(v) (v).begin(), (v).end() #define mkp(a, b) make_pair(a, b) using LL = long long; using VI = vector<int>; using VVI = vector<vector<int>>; using PII = pair<int, int>; using PIL = pair<int, LL>; using PLL = pair<LL, LL>; const double EPS = 1e-6; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const int N = 1e5 + 7; int n, x, W; int s[N], w[N]; int ans; void dfs(int idx, int r) { if (r >= ans || r > x) return; if (idx >= n + 1) { ans = min(ans, r); return; } for (int i = 1; i <= r; ++i) { if (w[idx] + s[i] <= W) { s[i] += w[idx]; dfs(idx + 1, r); s[i] -= w[idx]; } } s[r + 1] = w[idx]; dfs(idx + 1, r + 1); s[r + 1] = 0; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &x, &W); int flag = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); if (w[i] > W) flag = 1; } if (flag) { puts("No"); continue; } sort(w + 1, w + n + 1, greater<int>()); memset(s, 0, sizeof s); ans = INF; dfs(1, 1); if (ans <= x) puts("Yes"); else puts("No"); } return 0; }
简化
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define it insert #define pob pop_back #define pub push_back #define emb emplace_back #define all(v) (v).begin(), (v).end() #define mkp(a, b) make_pair(a, b) using LL = long long; using VI = vector<int>; using VVI = vector<vector<int>>; using PII = pair<int, int>; using PIL = pair<int, LL>; using PLL = pair<LL, LL>; const double EPS = 1e-6; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const int N = 1e5 + 7; int n, x, W; int s[N], w[N]; bool dfs(int idx) { if (idx >= n + 1) return 1; for (int i = 1; i <= min(idx + 1, x); ++i) { if (s[i] + w[idx] <= W) { s[i] += w[idx]; if (dfs(idx + 1)) return 1; s[i] -= w[idx]; } } return 0; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &x, &W); int flag = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); if (w[i] > W) flag = 1; } if (flag) { puts("No"); continue; } sort(w + 1, w + n + 1, greater<>()); memset(s, 0, sizeof s); if (dfs(0)) puts("Yes"); else puts("No"); } return 0; }