Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 3 of 3
  1. #1
    Regular Coder
    Join Date
    Apr 2006
    Location
    Northbrook, IL
    Posts
    394
    Thanks
    8
    Thanked 6 Times in 6 Posts

    Question 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
    Last edited by Leeoniya; 10-02-2008 at 04:49 AM.

  • #2
    Senior Coder rnd me's Avatar
    Join Date
    Jun 2007
    Location
    Urbana
    Posts
    4,401
    Thanks
    11
    Thanked 595 Times in 575 Posts
    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; }
    }
    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
    my site (updated 13/9/26)
    BROWSER STATS [% share] (2014/9/03) IE7:0.1, IE8:4.6, IE11:9.1, IE9:3.1, IE10:3.0, FF:17.2, CH:46, SF:11.4, NON-MOUSE:38%

  • #3
    Regular Coder
    Join Date
    Apr 2006
    Location
    Northbrook, IL
    Posts
    394
    Thanks
    8
    Thanked 6 Times in 6 Posts
    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
    •