Problem B: 运货卡车
"
| 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