View Full Version : anyone familiar with maximization algorithms or dynamic programming?

10-02-2008, 05: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".


rnd me
10-03-2008, 12:36 AM
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

10-04-2008, 12:33 AM
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)...

thanks anyways,