这题的总体思路是：二分答案+贪心+dfs验证

贪心：求前缀去掉无用的木板，缩小二分范围

二分答案:二分查找能符合要求的最多的木板数量

dfs验证：1.有序化，从大到小搜索（大的满足条件的少，这样可以减少搜索树上层结点）

2.对于相邻的两块所需要的木板，如果长度相等，那么强制从上一次放的那一块开始枚举，显然这样对答案是没有影响的，可以避免重复运算

3.可行性：对于一块已有的木板，如果其裁掉一部分后剩余部分小于目前需要的最小木板，则剩下的部分浪费。若waste(浪费的长度)+所需要的木板总长度>提供的木板总长度，方案不可行

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, a[N], b[N], ta[N], s[N], ans, sum, mid, t;
// t是多余的木材，sum是总共能提供的木材的量，s[N]是147需要的木材的前缀和
int dfs(int last, int x)
{
    if (x == 0) // x=0表示还需要0根，也就是可以满足条件了，那么返回1
    {
        return 1;
    }
    if (t + s[mid] > sum) // waste+所需要的木板总长度>提供的木板总长度,说明方案不可行
    {
        return 0;
    }
    for (int i = last; i <= n; i++)
    {
        if (ta[i] >= b[x]) //如果第i根木材可以满足147需要的第x根木材，则dfs
        {
            ta[i] -= b[x];
            if (ta[i] < b[1]) //比所需要的木板中最段的还短，那剩余部分就浪费了
            {
                t += ta[i];
            }
            if (b[x - 1] == b[x])
            {
                if (dfs(i, x - 1)) //这一步其实就是去重
                {
                    return 1;
                }
            }
            else if (dfs(1, x - 1)) //往下搜索
            {
                return 1;
            }
            if (ta[i] < b[1]) //还原状态
            {
                t -= ta[i];
            }
            ta[i] += b[x];
        }
    }
    return 0;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]), sum += a[i]; //计算提供的木板长度总和
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &b[i]);
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    for (int i = 1; i <= m; i++)
    {
        s[i] = s[i - 1] + b[i]; //计算前缀和，注意一定要在排序后计算哦！
    }
    while (sum < s[m])
    {
        m--; //如果选最短的m根都超出了能提供的木材的范围，则一定不可行,这一步就是通过贪心缩小二分的右边界的，减小时间复杂度
    }
    int L = 1, R = m;
    while (L <= R) //二分答案
    {
        for (int i = 1; i <= n; i++)
        {
            ta[i] = a[i]; //把a数组赋值给ta数组
        }
        t = 0;
        mid = (L + R) / 2;
        if (dfs(1, mid))
        {
            L = mid + 1, ans = mid;
        }
        else
        {
            R = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}