有n个宝藏要放入容量为C的背包中,这n个宝藏的重量分别为 s1,s2,s3....sn 为了减少成本,使用最少的背包装这些宝藏.
比如 : 有6个宝藏重量分别是 : 6, 9, 4, 10, 9, 1 背包容量为10,那么就需要4个背包

输入
n(0<n<=1000)表示宝藏个数以及s1,2,s3.....sn代表每个宝藏的重量,C代表一个背包的容量

输出
所需要的背包个数

样例输入
9
3 4 6 3 7 9 45 2 10
45

样例输出
2

怎么做？？

贪心解不了这道题。

那要用哪种方法？新手刚入门，求教

动态规划，背包算法

试了，可是没做出来

能不能帮我写一下

我觉得你都不用想该用什么现成的算法，不管是学过也好，听过也好，不知道也好。
人家说出来的名词，也会让你懵。你自己就是算法，思考思考如何做。
先拿一个包，装最大的。装了有余量，再尽量装最大的。没法装了就再拿一个包，反复进行。直至装完
6, 9, 4, 10, 9, 1
第一包：10
第二包：9,1
第三包：9
第四包:6,4

5 4 3 2 2 2 2
按照你的算法是 5+4、3+2+2+2、2，需要3个包
但实际上最佳的做法是 5+3+2、4+2+2+2，只需要2个包

收到的鲜花

• 郑鑫 于 2015-05-29 18:17 送鲜花  3朵  

多谢指误。
/汗 优化解

这个有点挑战，应该递归穷举：装载数量最多，重量最接近的吧。