装货物

装货物

思路

显然对每个物品我们有两种操作，与已经放好了的放在一起，或者新开一个盒子来放，由于数据比较小，我们可以直接稍加剪纸的爆搜即可。

第一个优化，当的时候立即返回。
第二个优化，给定的序列从大到小排个序，这样我们就能保证后面的决策会较少的重复利用前面已经放号的盒子，减少回溯成本。

代码

/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define endl '\n'
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')    f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

const int N = 30;

int a[N], sum[N], ans, n, w, x;

void dfs(int pos, int room) {
    if(room >= ans) return ;
    if(pos == n + 1) {
        ans = min(ans, room);
        return ;
    }
    for(int i = 1; i <= room; i++) {
        if(sum[i] + a[pos] <= w) {
            sum[i] += a[pos];
            dfs(pos + 1, room);
            sum[i] -= a[pos];
        }
    }
    sum[room + 1] = a[pos];
    dfs(pos + 1, room + 1);
    sum[room + 1] = 0;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = read();
    while(T--) {
        n = read(), x = read(), w = read();
        int flag = 0;
        for(int i = 1; i <= n; i++) {
            a[i] = read();
            if(a[i] > w) flag = 1;//这里得特判，不然就会wa
        }
        if(flag) {
            puts("No");
            continue;
        }
        memset(sum, 0, sizeof sum);
        sort(a + 1, a + 1 + n, greater<int> ());
        ans = inf;
        dfs(1,0);
        puts(ans <= x ? "Yes" : "No");
    }
    return 0;
}