Find the biggest sum from sequence of number which within a range

1,376

This is a special case of the knapsack problem in which the value of each item is equal to its weight. It's often called a subset sum problem, but unfortunately the latter term is also used for another problem (finding a subset that sums precisely to a given integer).

The slides by Carl Kingsford, based on Section 6.4 of Algorithm Design by Kleinberg & Tardos, give an accessible introduction to this (well-studied) problem, with pseudocode algorithm quoted below. The algorithm considers the two-parameter family of problems $\mathrm{Opt}(j,w)$ which seeks the sum of at most $w$ among the first $j$ integers. If the original problem is $\mathrm{Opt}(n,W)$, the algorithm solves $\mathrm{Opt}(j,w)$ for all $j\le n$ and $w\le W$

SubsetSum(n, W):
Initialize M[0,w] = 0 for each w = 0,...,W
Initialize M[i,0] = 0 for each i = 1,...,n
For i = 1,...,n: 
 For w = 0,...,W: 
  If w[i] > w: 
     M[i,w] = M[i-1,w]
  M[i,w] = max( M[i-1,w], w[j] + M[i-1, W-w[j]] )
Return M[n,W]
Share:
1,376

Related videos on Youtube

David Aditya
Author by

David Aditya

I love to code, I love to share, I love to solve everything with logic, and stackoverflow is my best friend

Updated on August 01, 2022

Comments

  • David Aditya
    David Aditya over 1 year

    I need help. How do I find the greatest sum from sequence of number within a finite range, for example: Given sequence {2,5,4,3,6} and the range is 11, so how to find the number within the sequence which the sum is less than or same with 11. ex: 5 and 6. Note : the result must not greater than the range

    Thanks for your help....

    • MJD
      MJD over 10 years
      Do you mean that you are given a set of numbers, say $\{2,5,4,3,6\}$, and a target, say 11, and you want to fund the subset that adds as close as possible to the target without exceeding it? So for $\{2,5,4\}$ and a target of 10, the solution would be 5+4=9?
    • David Aditya
      David Aditya almost 10 years
      yes right :) but the solution is in a range ex:2 number, 3 number, etc
  • David Aditya
    David Aditya almost 10 years
    yes, thanks for the answer and a good reference :)