choosing N object from set of M&gt;N maximizing overall ratio value/weightI have a set of M objects each with a certain value and weight. From this set I want to take out N objects ( N &lt; M of course) and maximize the ratio:total value of the N objects / total weight of the N objectsIt's a kind of an optimal selection problem.My intuition tells me to choose the N objects with the highest value/weight ratio, that is sort the M objects according to this ratio in descending order and take the first N objects in the sorting sequence.How can I demonstrate doing this will always yield the maximum total ratio?My attempt: if optimal ratio is a b for a certain selection of K objects and I have to add a K + 1 object, between one with a ratio x y and another with ratio w z , given that x y &gt; w z is the former always an optimal choice?I thought the problem could algebrically be reduced to this: given a , b positive constants, and x , y , w , z all positive so that: x y &gt; w z can or can never be that: a + x b + y &lt; a + w b + z I am not able to answer this point, please help!

Question

choosing N object from set of M&amp;gt;N maximizing overall ratio value/weightI have a set of M objects each with a certain value and weight. From this set I want to take out N objects (  N  &amp;lt;  M of course) and maximize the ratio:total value of the N objects / total weight of the N objectsIt&#039;s a kind of an optimal selection problem.My intuition tells me to choose the N objects with the highest value/weight ratio, that is sort the M objects according to this ratio in descending order and take the first N objects in the sorting sequence.How can I demonstrate doing this will always yield the maximum total ratio?My attempt: if optimal ratio is       a    b   for a certain selection of   K objects and I have to add a   K  +  1 object, between one with a ratio       x    y   and another with ratio       w    z  , given that      x    y    &amp;gt;      w    z  is the former always an optimal choice?I thought the problem could algebrically be reduced to this: given   a  ,  b positive constants, and   x  ,  y  ,  w  ,  z all positive so that:      x    y    &amp;gt;      w    z  can or can never be that:            a      +      x              b      +      y        &amp;lt;            a      +      w              b      +      z      I am not able to answer this point, please help!

Mihevcekd · Accepted Answer

11      20        &amp;gt;            1      2       but                     2        +        11                    3        +        20              &amp;lt;                    2        +        1                    3        +        2            so if you are choosing    N  =  2 out of             2      3        ,            11      20        ,            1      2       then your suggest algorithm will be suboptimal.

Brooke Kramer · Accepted Answer

Supponse   M  =  2 and you have one item with very large weight   w and very large value   v, such that the ratio   v      /    w is maximal by a large amount for this item. Then if you are forced to take another item, usually your best bet will be to choose the item with a very small weight, so that the ratio is relatively unchanged. This is true even if the value/weight ratio for the low weight item is not as good as the value/weight ratio for a much higher weight item.

choosing N object from set of M>N maximizing overall ratio value/weight I have a set of M objects e

Answered question

Answer & Explanation

New Questions in Pre-Algebra