https://ac.nowcoder.com/acm/contest/7189/A
题意:有 n 件货物, 第 i 件重 wi 吨,另有 x 个集装箱,每个集装箱可以装重量不超过 W 吨的货物。 货物不能分拆,判断这 x 个集装箱能否装下所有货物。
状压dp
f[s] 表示已装车的货物情况为 s 时最小需要的集装箱数量。
g[s] 表示已装车的货物情况为 s 时最后一个集装箱最大剩余空间。
则对于 s ,遍历每一个为 1 的位,判断如果能状态 t 最后一个集装箱装下这个货物,则箱数等于 t 的,否则等于 t 的+1,取最小值得到 s 的 f 值。最后再遍历所有取到最小值的情况,更新 g。
关键的一点在于遍历所有取到最小值的情况更新 g,如果某一情况的箱子数大于最小值,则即使它剩余的空间很大,也不行,因为最小值可以再开一个空箱子。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 5e5 + 10; const ll mod = 1e9 + 7; int T; int n, x, w; int f[1 << 23], g[1 << 23], a[N], tmp[100]; int main() { scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &x, &w); for (int i = 0; i <= (1 << n); i++) { f[i] = INF; g[i] = 0; } bool ck = 1; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > w)ck = 0; } if (!ck) { puts("No"); continue; } f[0] = 0; g[0] = 0; for (int s = 1; s < (1 << n); s++) { for (int i = 0; i < n; i++) { if (s >> i & 1) { int t = (s ^ (1 << i)); if (g[t] >= a[i])tmp[i] = f[t]; else tmp[i] = f[t] + 1; f[s] = min(f[s], tmp[i]); } } for (int i = 0; i < n; i++) { if (s >> i & 1) { int t = (s ^ (1 << i)); if (tmp[i] == f[s]) { if (g[t] >= a[i])g[s] = max(g[s], g[t] - a[i]); else g[s] = max(g[s], w - a[i]); } } } } if (f[(1 << n) - 1] <= x)puts("Yes"); else puts("No"); } return 0; }
|