Leeoniya

10-02-2008, 04:30 AM

i'm looking to make a calculator that would determine the minimum combination of numbers (from a predefined set) which when summed must be greater than a lower bound value and also must not exceed an upper bound value.

i have made a "greedy" algo for this, but it is not optimal. from doing some reading this is something that would require "dynamic programming".

thanks,

Leon

rnd me

10-02-2008, 11:36 PM

var set = [ 3,5,8,4,2,9,6,8,1,9 ]

function sum(r){var t=0; for(var i=0, mx=r.length; i<mx;i++){t=t+r[i];}return t;}

function computMinSet(r, l, u){

var tot = [];

var r2 = r.sort(function(a,b){return b-a;});

for(var i=0; sum(tot)<u; i++ ){

tot.push( r2[i] );

if(sum(tot)>u){ tot.pop();}

if(sum(tot)>l){ break; }

}

return tot;

}

computMinSet(set, 10, 35)// 9,9

computMinSet(set, 25, 55)// 9,9,8

computMinSet(set, 30, 50)// 9,9,8,8

computMinSet(set, 10, 12)// 9,3

Leeoniya

10-03-2008, 11:33 PM

i guess i forgot to mention that any numbers in the set can be reused, so duplicates really dont make a difference.

and also the sum needs to get as close to the upper bound value as possible without exceeding it. while also minimizing the amount of numbers used in the process.

the algo u posted is a pretty much what i have now (greedy)...

http://en.wikipedia.org/wiki/Greedy_algorithm

thanks anyways,

Leon