现有N个货物,每个货物重量不等,还有一个货箱,货箱能承受的重量为M。要求从货物中取出若干件装入这个货箱里,使所有货物的总重最接近M但不超过M。
例如:有10件货物,编号1、2、3……10,重量分别为1、2、3……10,货箱承受重量为30。列出最佳货物组合!
最好能说下原理和源码,不胜感激~!
好吧,对于 烂掉の萝卜 和 ljwco 的算法,我举2个反例:
1、共有3个货物,重量分别是25、17、10,货箱承重30。按照你们的算法,首先是25<30,然后25+17>30,最后25+10>30,得出的结果是25,但是显然,最优方案是17+10=27!
2、共有3个货物,重量分别是27、15、10,货箱承重30。首先10<30,然后10+15<30,最后10+15+27>30,得出结果是10+15=25,但是显然,最优方案是27!
我还是问一下组合数C(m,n)的所有组合的枚举算法吧……