1921_算法设计例题：装载问题（回溯、分枝限界）

有一批概共n个集装箱要装上两艘载重量分别为c₁和c₂的轮船，其中，集装箱i的重量为w_i，且。

装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船。

输入的第一个为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是集装箱个数n（ n ≤ 20 ），第二行是两个整数c₁和c₂，表示两艘轮船的载重量，接下来n行，每行一个整数w_i，表示第i个集装箱的重量，（ 0 < w_i < 1000，i = 1, 2, …, n， 0 < c₁, c₂ < 30000 ）

对应每个测试样例输出两行，第一行格式为"Case #:"，其中'#'表示第几个测试样例（从1开始计）。

第二行格式为：如果找不到合理的装载方案，则输出"No"，否则输出最优载重量。

2
3
50 50
10 40 40
3
50 50
20 40 40

Case 1:
50
Case 2:
No

容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案：
1. 首先将第一艘轮船尽可能装满；
2. 将剩余的集装箱装上第二艘轮船。