思路
二分+搜索+剪枝。
首先二分一个答案，表示最多可以切出x块。（一个结论：切出的一定是从较小的前x块。如果一个木材可以满足很多个需要的木材，那么切出最小的，就意味着以后再选时的机会更多。）
然后暴力搜索前x块分别由哪个木材切出。
剪枝1：如果所有提供的木材加起来也不能满足需要的木材，直接跳过
剪枝2：记录一下浪费掉的木材（即一块木材切掉了一些后，剩下的木材中连最小的也切不出了的），如果提供的木材总量-浪费掉<当前所有的木材需要的，直接跳过。
剪枝3：当前需要的和下一块需要的木材是一样长的，那么不必从第一块开始搜索了，直接从上次搜索到的地方开始。
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 5 using namespace std; 6 7 const int N = 10010; 8 int n,m,rest,tot; 9 int a[N],b[N],c[N],sum[N]; 10 11 inline int read() { 12 int x = 0,f = 1;char ch = getchar(); 13 for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1; 14 for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0'; 15 return x * f; 16 } 17 bool dfs(int now,int s) { // 当前需要的木材，从给出的木材中第s个开始 18 if (!now) return true; 19 if (rest+sum[now] > tot) return false; // 剪枝2 20 for (int i=s; i<=m; ++i) { // 枚举所有给出的木材 21 if (c[i] >= b[now]) { // 当前木材可以切出需要的 22 c[i] -= b[now]; //- 23 if (c[i] < b[1]) rest += c[i]; 24 if (b[now]==b[now-1]) { 25 if (dfs(now-1,i)) return true; 26 } 27 else {if (dfs(now-1,1)) return true;} // 剪枝3 28 if (c[i] < b[1]) rest -= c[i]; 29 c[i] += b[now]; // - 30 } 31 } 32 return false; 33 } 34 bool check(int x) { 35 for (int i=1; i<=m; ++i) c[i] = a[i]; 36 rest = 0; 37 return dfs(x,1); 38 } 39 int main() { 40 m = read(); 41 for (int i=1; i<=m; ++i) a[i] = read(),tot += a[i]; 42 sort(a+1,a+m+1); 43 n = read(); 44 for (int i=1; i<=n; ++i) b[i] = read(); 45 sort(b+1,b+n+1); 46 for (int i=1; i<=n; ++i) sum[i] = sum[i-1] + b[i]; 47 48 while (sum[n] > tot) n--; // 剪枝1 49 int L = 0,R = n,ans; // L有等于0的情况！ 50 while (L <= R) { 51 int mid = (L + R) / 2; 52 if (check(mid)) L = mid + 1,ans = mid; 53 else R = mid - 1; 54 } 55 cout << ans <<' '; 56 return 0; 57 }