From: israel@math.ubc.ca (Robert Israel)
Subject: Re: Minimization problem
Date: 20 Aug 1999 20:08:22 GMT
Newsgroups: sci.math
Keywords: Dynamic Programming

In article <7ph7s5$p2h$1@eveningstar.space.gc.ca>,
 "Emanuel Matos" <emanuel.matos@space.gc.ca> writes:
> Can someone help me? I have an interesting problem.
 
> I have a list of 71 items, each with a fixed Value and Price
> e.g. item number 11 has a value of 22 and a price of 25.
> Some items can have the same value and price. e.g. item 42
> also has a value of 22 and a price of 25.)
> 
> What I would like to calculate is as follows:
> 
> Minimize the total price subject to the constraint that the sum of the
> values = 100

Since you talk about items 11 and 42 having the same value and price, I 
assume that each item can be used only once (otherwise they would be
considered the same item).

This is ideally suited for Dynamic Programming.  
Let p_m and v_m be the price and value of item #m.
Let X(m,n) be the minimum total price for items chosen from numbers 1 to m, 
subject to the total value being n.  If total value n is unattainable for 
these items, X(m,n) = infinity (or in practice some very large number).  
Then: 
X(m,0) = 0 for m >= 0
X(0,n) = infinity for n > 0 
X(m,n) = min(X(m-1,n), X(m-1,n-v_m) + p_m) for m > 0

Use this recursion to calculate X(m,n) for 0 <= m <= 71 and 0 <= n <= 100.
Very easy and fast on a computer (you can probably do it on a spreadsheet).
Then work backwards from X(71,100) to see which items are chosen.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2