Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: anyone familiar with maximization algorithms or dynamic programming?

1. ## anyone familiar with maximization algorithms or dynamic programming?

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

• Code:
```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; }
}
}

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```

• 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

•

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•