超超级难的问题！非高手莫进！！

Question

问题是这样的：   有一个包，只能装 V kg 的东西！现在有 n 种东西可以选择装，但是他们的价值和重量都不一样.
X1 重a1 kg ,每个价值 b1 ;
X2 重a2kg,价值b2;
................
Xn 重an Kg,价值bn问题是怎么样才能使包装的东西价值最大！
欢迎大家讨论，怎么用编程的方法求解？？？有实际价值者都可以得分的！

Answer 1

首先求出每个X的权： Qn = bn / an ;然后，排出两个队列：一个按权Q开始排序list1，另一个按重量a开始排序list2，从权Q最大的Xn开始装，下一个可以装的是xn在list2中的xn下第一个满足重量要求
的Xm。

Answer 2

这是一个普通的线性规化问题.可以这样描述
求 Yi  (i = 1...n)
ST.  Max( Y1*B1 + Y2*B2 + ... + Yn*Bn)
满足条件:
Yi*A1 + Y2*A2 + ... Yn*An <= V
其中 Yi Ai Bi都非负

Answer 3

呵呵!大家好呀!!!其实这个问题很简单,大家好象都把他搞复杂了!
wistaria(听风听雨) :说的很正确的了.确实是一个线形规划的问题!
但是我认为假如用动态规划的来解决的话可能还要简单一些的了,
因为这个也是一个整数规划的问题,因为Yi都只有可能取整数!所以用线形规划的方法去解的话,可能很麻烦.用整数规划的方法解的话,和穷尽法没有什么区别了.很慢!所以我一直想用动态规划的方法去解.但是现在我还没有能够做出这样一个工作,不知道哪个高手能够点拨我一下!
前面wistaria(听风听雨) 的方法我也想过,但是我发现有一些问题,不能够得到最优解的.
对以上两个人的回答我会在结帐的时候加分的了.欢迎大家继续讨论了!!!