description:
n个物品 x个可容纳体积为w的箱子 问n个物品是否能全部装进箱子内 物品不可拆分
solution:
n只有21 可以状压dp或者dfs 这里直接采用dfs 先预处理x个箱子的体积为w 然后从第一个物品开始搜
加上一些剪枝 从大的开始放 你大的肯定没有小的更加灵活 所以大的先存
code:
#include <bits/stdc++.h> using namespace std; #define LL long long #define ULL unsigned long long #define mes(x, a) memset(x, a, sizeof(x)); #define sca(a) scanf("%d", &a) #define lowbit(x) x&(-x) #define mk make_pair #define pb(x) push_back(x) #define all(x) (x).begin(), (x).end() #define fi first #define se second #define lson v << 1 #define rson v << 1 | 1 #define pii pair<int, int> int a[25], b[25]; int n, x, w; bool f = 0; void dfs(int now) { if (f) { return; } if (now == n + 1) { f = 1; return; } bool in = 0; for (int i = 1; i <= min(now, x); i++) { if (b[i] >= a[now]) { b[i] -= a[now]; dfs(now + 1); if(f){ return ; } b[i] += a[now]; in = 1; } } if(!in)return ; } int main() { ios::sync_with_stdio(0); int T; cin >> T; while (T--) { cin >> n >> x >> w; LL sum = 0; bool flag = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; if (a[i] > w) { flag = 1; } b[i] = w; } sort(a + 1,a + 1 + n,greater <int>()); if (sum > 1LL * n * w || flag) { cout << "No" << '\n'; } else { f = 0; dfs(1); if (f) { cout << "Yes"; } else { cout << "No"; } cout << '\n'; } } return 0; }