#LQ1493. 背包问题
背包问题
问题描述
小蓝是一位狂热的积木爱好者,家里堆满了自己用积木组装的建筑模型。最近,有两款新出的积木组件上市,小蓝自然不会错过,他带上了自己的三个背包来到了积木商城,打算将尽可能多的积木组件带回家,每个背包都有一个固定的空间大小。小蓝只会购买这两种新出的积木组件 和 , 和 各自会占用背包的一部分空间,但对于同一种类型的积木占用的空间是相同的。小蓝想知道自己最多能带走多少数量的积木组件。
可以认为小蓝有足够的货币,只要背包可以装下的积木他都有能力购买。商场内的积木数量也是有限制的。
输入格式
输入的第一行包含一个整数 ,表示有 组独立的询问。
每一组询问由三行组成。
每组询问的第一行包含三个整数 ,相邻的整数之间使用一个空格分隔,表示三个背包的空间大小。
每组询问的第二行包含两个整数 ,用一个空格分隔,分别表示商场内积木组件 和 的总量。
每组询问的第三行包含两个整数 ,用一个空格分隔,分别表示每个积木组件 和 所占用的空间大小。
输出格式
输出 行,每行包含一个整数表示答案。
样例
3
2 2 3
1 2
1 2
3 8 3
3 4
4 2
6 8 7
10 10
5 1
3
5
12
样例说明
对于第一组询问,第一个背包装一个 积木,无剩余空间;第二个背包装一个 积木,无剩余空间;第三个背包装一个 积木,剩余 空间,但积木已经没有了;最终答案是 ,可以带走所有的积木。
对于第二组询问,第一个背包和第三个背包各自装一个 组件,第二个背包装两个 组件和一个 组件,答案是 。
对于第三组询问,第一个背包:;第二个背包:;第三个背包:。答案是 。
评测用例规模与约定
对于 的评测用例, ;
对于所有评测用例,, ,,。
相关
在以下作业中: