Maximum sum in an array subject to a constraint

Question

How do you find the maximum sum <= K in an array with no other constraints (elements don't have to be contiguous or non-contiguous)

chill · Accepted Answer · 2013-12-15 20:02:46Z

1

This can be solved using the dynamic programming algorithm for the 0/1 knapsack problem with element values set equal to element weights.

answered Dec 15, 2013 at 20:02

chill

17k2 gold badges42 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

amit · Accepted Answer · 2013-12-15 20:00:46Z

1

This is a variation of the subset sum problem.

This problem is NP-Complete, so there is no known polynomial solution.
However, if your list contains relatively small integers, there is an efficient Dynamic Programming pseudo-polynomial solution.

Other alternative is checking all 2^n possible subsets and checking the best out of them.

answered Dec 15, 2013 at 20:00

amit

179k27 gold badges245 silver badges348 bronze badges