哪位大哥帮帮我吧！

第 33 题  ：  船长的烦恼
(时间限制为：500毫秒)
李船长买了艘船跑运输，开业的第一天就遇到一个烦恼。顾客有一大批货物要运输到某地，这批货物由若干种物品构成，每种物品有不同的重量。顾客要求每种物品要么全装，要么不装。李船长和顾客已讲好运费根据重量来计算，但对于装哪些物品则由李船长自己定。为了尽量装下最多物品（不超载），以多赚运费，李船长拿着货物清单求助于程序高手的你帮忙解决，以求出他的船能装的最重的重量。例如有三件物品，分别重40,20,45顿。船的载重为50顿，则李船长能装的最重重量为45顿。
输入：
    输入第一行为正整数n(1<=n<=100),表示用例个数，接下来有2n行，每两行为一个用例，其中第一行包含两个正整数m（1<=m<=10）、w(0<=w<=10000)，m表示物品种数，w表示船的载重量。
输出：
    对每一个用例，用一行输出船所能装载的最大重量。
输入样例：
2
3 50
40 20 45
5 10
3 6 5 8 11
输出样例：
45
9
这个题目给个思路吧！
谢谢！

10 个解决方案

#1

google背包问题

#2

引用 1 楼 hai040 的回复:

google背包问题

 什么意思啊

#3

引用 1 楼 hai040 的回复:

google背包问题

登录google.com, 输入“背包问题”，然后按Enter键。

#4

哈哈~~~ LZ加油！

引用 3 楼 cl22333 的回复:

引用 1 楼 hai040 的回复:

google背包问题


登录google.com, 输入“背包问题”，然后按Enter键。

#5

呵呵，我是新手，现在才进大一，但发现我的C++老师帮不了我（每科都是），这大学老师不怎么管事啊，但我热爱C++，我会坚持走这条路，所以希望大家不吝指教，帮帮我这个充满希望的少年。

#6

引用 5 楼 xtzhangxian 的回复:

呵呵，我是新手，现在才进大一，但发现我的C++老师帮不了我（每科都是），这大学老师不怎么管事啊，但我热爱C++，我会坚持走这条路，所以希望大家不吝指教，帮帮我这个充满希望的少年。

现在大学老师工资比中学老师还低,所以如果认真管事的话就吃不饱饭了~~~

#7

引用 5 楼 xtzhangxian 的回复:

呵呵，我是新手，现在才进大一，但发现我的C++老师帮不了我（每科都是），这大学老师不怎么管事啊，但我热爱C++，我会坚持走这条路，所以希望大家不吝指教，帮帮我这个充满希望的少年。

大一就开C++啊 不是要先开C吗

#8

引用 7 楼 sonnno 的回复:

引用 5 楼 xtzhangxian 的回复:

呵呵，我是新手，现在才进大一，但发现我的C++老师帮不了我（每科都是），这大学老师不怎么管事啊，但我热爱C++，我会坚持走这条路，所以希望大家不吝指教，帮帮我这个充满希望的少年。



大一就开C++啊 不是要先开C吗

LZ是学计算机的吧。一般大一上学期开C 下学期就开C++了~ 主要还是靠自己吧~  实在有问题再求助~

#9

ACM?

#10

哦，我大一开的确实是C++,这个号我刚申请的，怎么评分啊！是不是“丢个板砖”啊，还是直接点“结贴”?