Find the biggest sum from sequence of number which within a range
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]
Related videos on Youtube
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, 2022Comments
-
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 over 10 yearsDo 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 almost 10 yearsyes right :) but the solution is in a range ex:2 number, 3 number, etc
-
-
David Aditya almost 10 yearsyes, thanks for the answer and a good reference :)