#P18315. Bin Packing
Bin Packing
Bin Packing
今天来解决一个经典的 NP 难问题:装箱。
有 个物品,第 个物品的大小为 ,其中 。你有若干容量为 的箱子。同一个箱子可以放入多个物品,当且仅当这些物品的大小之和不超过 。
求装下全部 个物品所需的最少箱子数。
本题对输入有特殊约定:
- 对于所有非样例测试文件,测试用例数和每个测试用例的物品数固定为 。
- 物品大小随机生成。严格来说,每个 都从整数集合 中独立、均匀地随机选取。
输入格式
第一行包含整数 ,表示测试用例数。
对于每个测试用例:
- 第一行包含整数 ,表示物品数。
- 第二行包含 个整数 ,表示每个物品的大小。
输出格式
对于每个测试用例,输出一行,包含装下全部物品所需的最少箱子数。
数据范围与生成保证
对于所有非样例测试:
- ;
- ;
- ;
- 每个 都是从 内的整数中独立均匀生成的。
样例
输入
10
5
8 2 2 3 9
3
11 1 1
8
9 8 2 3 4 2 2 12
10
2 2 2 2 2 2 3 3 3 3
6
5 2 8 4 1 11
8
12 12 9 8 2 8 4 4
5
5 5 6 6 6
8
10 12 5 4 8 2 2 11
7
5 1 5 7 9 4 4
6
12 1 1 9 3 5
输出
2
2
4
2
3
5
3
5
4
3
说明
第一个测试用例可以如下分配:
- 箱子 1 放入第 个物品,总大小恰好是 。
- 箱子 2 放入第 个物品,总大小恰好是 。
因此,两个箱子足够。