题目描述
小蓝是一位狂热的积木爱好者，家里堆满了自己用积木组装的建筑模型。最近，有两款新出的积木组件上市，小蓝自然不会错过，他带上了自己的三个背包来到了积木商城，打算将尽可能多的积木组件带回家，每个背包都有一个固定的空间大小。小蓝只会购买这两种新出的积木组件 $A$ 和 $B$，$A$ 和 $B$ 各自会占用背包的一部分空间，但对于同一种类型的积木占用的空间是相同的。小蓝想知道自己最多能带走多少数量的积木组件。
可以认为小蓝有足够的货币，只要背包可以装下的积木他都有能力购买。商场内的积木数量也是有限制的。
输入格式
输入的第一行包含一个整数 $T$，表示有 $T$ 组独立的询问。
每一组询问由三行组成。
每组询问的第一行包含三个整数 $B_{1}, B_{2}, B_{3}$，相邻的整数之间使用一个空格分隔，表示三个背包的空间大小。
每组询问的第二行包含两个整数 $cnt_{A}, cnt_{B}$，用一个空格分隔，分别表示商场内积木组件 $A$ 和 $B$ 的总量。
每组询问的第三行包含两个整数 $V_{A}, V_{B}$，用一个空格分隔，分别表示每个积木组件 $A$ 和 $B$ 所占用的空间大小。
输出格式
输出 $T$ 行，每行包含一个整数表示答案。
输入输出样例 #1
输入 #1
```
3
2 2 3
1 2
1 2
3 8 3
3 4
4 2
6 8 7
10 10
5 1
```
输出 #1
```
3
5
12
```
说明/提示
样例说明
对于第一组询问，第一个背包装一个 $B$ 积木，无剩余空间；第二个背包装一个 $B$ 积木，无剩余空间；第三个背包装一个 $A$ 积木，剩余 $2$ 空间，但积木已经没有了；最终答案是 $3$，可以带走所有的积木。
对于第二组询问，第一个背包和第三个背包各自装一个 $B$ 组件，第二个背包装两个 $B$ 组件和一个 $A$ 组件，答案是 $5$。
对于第三组询问，第一个背包： $1 \\mathrm{~A}+1 \\mathrm{~B}$；第二个背包： $8 \\mathrm{~B}$ ；第三个背包： $1 \\mathrm{~A}+1 \\mathrm{~B}$。答案是 $12$。
评测用例规模与约定
– 对于 $30 \\%$ 的评测用例， $1 \\leq cnt_{A}, cnt_{B} \\leq 100$；
– 对于所有评测用例， $1 \\leq T \\leq 100$，$1 \\leq B_{1}, B_{2}, B_{3} \\leq 10^{9}$，$1 \\leq V_{A}, V_{B} \\leq 10^{9}$，$1 \\leq cnt_{A}, cnt_{B} \\leq 1,000$。
**[传送门](https://www.luogu.com.cn/problem/P12210)**
题意
小蓝有三个背包，容量分别是 $B_1$，$B_2$，$B_3$。现有两种积木 $A$ 和 $B$：
– $A$ 有 $cnt_A$ 个，每个占 $V_A$ 空间。
– $B$ 有 $cnt_B$ 个，每个占 $V_B$ 空间。
把每个积木数量限制内的 $A$ 积木和 $B$ 积木装进三个背包（每个背包的空间限制之内），问最多能带走多少个积木。
思路
~~看到题目中的背包时，感觉肯定是个背包（结果自己做不出来）。~~
点开算法标签，才发现是**枚举**，想出来是 $O(n^3)$，感觉能过。
首先枚举 $A$，我们依次枚举第一个背包、第二个背包、第三个背包中分别装入多少个 $A$。
第一层循环枚举背包 $1$ 中 $A$ 的数量 $i$ 需满足 $i \\le cnt_A$ 且 $i \\times V_A \\le B_1$。第二层循环枚举背包 $2$ 中 $A$ 的数量 $j$ 需满足 $i + j \\le cnt_A$ 且 $j \\times V_A \\le B_2$。第三层循环枚举背包 $3$ 中 $A$ 的数量 $k$ 需满足 $i+ j+ k \\le cnt_A$ 且 $k \\times V_A \\le B_3$。
接着贪心 $B$ 的数量，在每个背包的剩余空间中装入尽可能多的 $B$ ，但要注意，三个背包能装的 $B$ 的总数不能超过 $cnt_B$。因此，实际装入的 $B$ 的数量是取能装的数量和 $B$ 的总量的最小值。
所以，当前方案的答案就求出了，最后取所有方案的最大值。
代码 1
按照思路写出的。
#include<bits/stdc++.h>
using namespace std;
int t,bags[5],va,vb,a,b,ans=INT_MIN;
signed main()
{
cin>>t;
while(t–)
{
ans=INT_MIN;//多测要清空
cin>>bags[1]>>bags[2]>>bags[3]>>a>>b>>va>>vb;
for(int i=0;i<=a&&i*va<=bags[1];i++)//第一层枚举
{
int b1=min(b,(bags[1]-i*va)/vb);
for(int j=0;j<=a-i&&j*va<=bags[2];j++) //第二层枚举
{
int b2=min(b-b1,(bags[2]-j*va)/vb);
for(int k=0;k<=a-i-j&&k*va<=bags[3];k++) //第三层枚举
{
int b3=min(b-b1-b2,(bags[3]-k*va)/vb);
int cnt=(i+j+k)+(b1+b2+b3);
ans=max(ans,cnt);
}
}
}
cout<<ans<<'\\n';
}
return 0;//完结撒花
}
代码 2
~~丧心病狂的简化~~
#include<bits/stdc++.h>
using namespace std;
int t,bags[5],va,vb,a,b,ans=INT_MIN;
signed main()
{
cin>>t;
while(t–)
{
ans=INT_MIN;
cin>>bags[1]>>bags[2]>>bags[3]>>a>>b>>va>>vb;
for(int i=0;i<=a&&i*va<=bags[1];i++)
for(int j=0;j<=a-i&&j*va<=bags[2];j++)
for(int k=0;k<=a-i-j&&k*va<=bags[3];k++)
ans=max(ans,i+j+k+min(b,(bags[1]-i*va)/vb)+min(b-min(b,(bags[1]-i*va)/vb),(bags[2]-j*va)/vb)+min(b-min(b,(bags[1]-i*va)/vb)-min(b-min(b,(bags[1]-i*va)/vb),(bags[2]-j*va)/vb),(bags[3]-k*va)/vb));
cout<<ans<<'\\n';
}
return 0;//完结撒花
}
