Use dynamic programming to find a subset of numbers whose sum is closest to given number M

2
votes

Given a set A of n positive integers a1, a2,... a3 and another positive integer M, I'm going to find a subset of numbers of A whose sum is closest to M. In other words, I'm trying to find a subset A′ of A such that the absolute value |M - ???? Σ a∈A′| is minimized, where [ Σ a∈A′ a ] is the total sum of the numbers of A′. I only need to return the sum of the elements of the solution subset A′ without reporting the actual subset A′.

For example, if we have A as {1, 4, 7, 12} and M = 15. Then, the solution subset is A′ = {4, 12}, and thus the algorithm only needs to return 4 + 12 = 16 as the answer.

The dynamic programming algorithm for the problem should run in O(nK) time in the worst case, where K is the sum of all numbers of A.

2
dynamic-programmingknapsack-problemsubset-sum

2 Answers

1
votes

You construct a Dynamic Programming table of size n*K where

D[i][j] = Can you get sum j using the first i elements ?

The recursive relation you can use is: D[i][j] = D[i-1][j-a[i]] OR D[i-1][j] This relation can be derived if you consider that ith element can be added or left.

Time complexity : O(nK) where K=sum of all elements

Lastly you iterate over entire possible sum you can get, i.e. D[n][j] for j=1..K. Which ever is closest to M will be your answer.

1
votes

For dynamic algorithm, we

  1. Define the value we would work on

The set of values here is actually a table.

For this problem, we define value DP[i , j] as an indicator for whether we can obtain sum j using first i elements. (1 means yes, 0 means no)

Here 0<=i<=n, 0<=j<=K, where K is the sum of all elements in A

  1. Define the recursive relation

DP[i+1 , j] = 1 , if ( DP[i,j] == 1 || DP[i,j-A[i+1]] ==1)

Else, DP[i+1, j] = 0.

Don't forget to initialize the table to 0 at first place. This solves boundary and trivial case.

  1. Calculate the value you want

    Through bottom-up implementation, you can finally fill the whole table.

Now, things become easy. You just need to find out the closest value to M in the table whose value is one.

Here, just work on DP[n][j], since n covers the whole set. Find the closest j to M whose value is 1.

Time complexity is O(kn), since you iterate k*n times in total.