Question

求解一个VB编程难题

现有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）的所有组合的枚举算法吧……

Answer 1

我比较笨，就用笨的方法吧。源码太多不好写，知道原理自已就很容易写出来。
第一步：.把1--10货物按重量由大到小重新排列，把最重的放编号1，其次放编号2，以此类推，这样货物1为最重，货物2为第二重，同理，货物10为最轻。（这个排列的代码所有编程的书中例子都有）
第2 步：货物1与货箱比较，两种可能，
第1种可能：货1<货箱，则货物1+货物2结果再与货箱比较，如果小于货箱，则再加上货物3，结果与货箱比较；如果货1+货2>货箱，则货1+货3与货箱比较，这样一直找下去。
第2种可能：如果货物1<货箱，则同货物2同货箱比较，以此类推。
第3步：从第2步中的2种可能查找的结果是找到第一次多个货物可以放到货箱的组合，因为这个组合不一定是最佳的，所以，把这个组合存入你定义的一个二维数组中，把组合名存于a01，组合重量与货箱容量相减取绝对值存于a11，然后用第2步的方法换下一个货号来查找第二个组合，组合名存于a02，与货箱相减绝对值放于a12，以此类推，一直到第2步无解结束循环。
最后把a01,a02......从小到大排列，则第一个就是最佳组合，用它对应的组合名，即为最佳货物组合。

Answer 2

从10号货物往下加，10+9+8+。。。+N 一直到接近M
如果超过M的话，把N换成N-1号货物，如果还超出M
就换成N-2号货物。一直到最接近M为止
一定要从大到小相加才能做到最接近

不会是25的，你没有仔细看哦
如果是超出的话，应该换N-1的。
所以自然就是17+10了

Answer 3

还是2楼的技巧好

Answer 4

穷举法，呵呵，每种可能都试过来，好处是思路简单，缺点是效率低，10件货物可以是任意重量，修改数组就行了。代码没调试，随手想到哪就写上了，水平低高手表鄙视我，呵呵
dim huowu(10)
dim maxH
dim maxList
dim i(10)
dim j
dim sumI
i(1)=1
huowu(1)=1
huowu(2)=2
huowu(3)=3
huowu(4)=4
huowu(5)=5
huowu(6)=6
huowu(7)=7
huowu(8)=8
huowu(9)=9
huowu(10)=10
while i(10)<=10
sumI=0
for j=1 to 10
sumI=sumI+huowu(i(j))
next
if maxH<sumI then
maxH=sumI
maxList=""
for j=1 to 10
maxList=maxList+i(j)+" "
next
i(1)=i(1)+1
for j=1 to 9
if i(j)>10 then
i(j)=0
i(j+1)=i(j+1)+1
end if
next
end if
wend
print maxH
print maxList