#P18315. Bin Packing

Bin Packing

Bin Packing

今天来解决一个经典的 NP 难问题:装箱。

有 NN 个物品,第 ii 个物品的大小为 AiA_i,其中 1≤Ai≤121\le A_i\le12。你有若干容量为 1212 的箱子。同一个箱子可以放入多个物品,当且仅当这些物品的大小之和不超过 1212。

求装下全部 NN 个物品所需的最少箱子数。

本题对输入有特殊约定:

  1. 对于所有非样例测试文件,测试用例数和每个测试用例的物品数固定为 T=100,N=1000T=100,N=1000。
  2. 物品大小随机生成。严格来说,每个 AiA_i 都从整数集合 {1,2,…,12}\{1,2,\ldots,12\} 中独立、均匀地随机选取。

输入格式

第一行包含整数 TT,表示测试用例数。

对于每个测试用例:

  • 第一行包含整数 NN,表示物品数。
  • 第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N,表示每个物品的大小。

输出格式

对于每个测试用例,输出一行,包含装下全部物品所需的最少箱子数。

数据范围与生成保证

对于所有非样例测试:

  • T=100T=100;
  • N=1000N=1000;
  • 1≤Ai≤121\le A_i\le12;
  • 每个 AiA_i 都是从 [1,12][1,12] 内的整数中独立均匀生成的。

样例

输入

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 放入第 1,2,31,2,3 个物品,总大小恰好是 8+2+2=128+2+2=12。
  • 箱子 2 放入第 4,54,5 个物品,总大小恰好是 3+9=123+9=12。

因此,两个箱子足够。