Problem H: 运货卡车
| Time Limit |
$5$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$87$ |
正确数量 |
$64$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
动态规划 |
当前分类(单击移除)：
动态规划
单击选择分类：
在一个运输公司中有很多型号完全一样的卡车，每个卡车都可以装载重量为$w$的货物。有若干个需要运输的货物$a_n$，每个货物$a_i$都有一个质量$m_i$。这个运输公司对于这些货物的装载方式策略是，每一次尽可能装更多质量的货物，在有多种可以装载最多质量的货物的方式时，会选择货物下标字典序最小的一组。例如货物的质量为4 3 2 1，卡车能够装载的质量为5时，第一次会选择4 1而不是2 3。
第一行是一个整数$T$，代表测试数据的组数。每组样例中，第一行有两个整数$n$,$w$，代表有$n$个货物，每个卡车可以装载质量$w$的货物。接下来一行有$n$个数字，代表每个货物的质量。其中$T \le 20,n,w \le 1000$。每个货物的质量不会超过$w$。
2
4 4
3 3 3 3
4 4
2 2 2 2