Algorithm to select a set of numbers to reach a minimum total

Question

Given A set of numbers n[1], n[2], n[3], .... n[x] And a number M

I would like to find the best combination of

n[a] + n[b] + n[c] + ... + n[?] >= M

The combination should reach the minimum required to reach or go beyond M with no other combination giving a better result.

Will be doing this in PHP so usage of PHP libraries is ok. If not, just a general algorithm will do. Thanks!

Answer 1

This looks like a classic Dynamic Programming problem (also indicated by other answers mentioning its similarity to 0-1 Knapsack and Subset Sum problems). The whole thing boils down to to one simple choice: for each element in the list, do we use it in our sum or not. We can write up a simple recursive function to compute the answer:

f(index,target_sum)=
     0     if target_sum<=0 (i.e. we don't need to add anymore)
     infinity   if target_sum>0 and index is past the length of n (i.e. we have run out of numbers to add)
     min( f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index] )    otherwise (i.e. we explore two choices -  1. take the current number 2. skip over the current number and take their minimum)

Since this function has overlapping subproblems (it explores the same sub-problems over and over again) , it is a good idea to memoize the function with a cache to hold values that were already computed before.

Here's the code in Python:

#! /usr/bin/env python

INF=10**9 # a large enough number of your choice

def min_sum(numbers,index,M, cache):
    if M<=0: # we have reached or gone past our target, no need to add any more
        return 0
    elif len(numbers)==index: # we have run out of numbers, solution not possible
        return INF
    elif (index,M) in cache: # have been here before, just return the value we found earlier
        return cache[(index,M)]
    else:
        answer=min(
            min_sum(numbers,index+1,M,cache), # skip over this value
            min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value
        )
        cache[(index,M)]=answer # store the answer so we can reuse it if needed 
        return answer 

if __name__=='__main__':
    data=[10,6,3,100]
    M=11

    print min_sum(data,0,M,{})

This solution only returns the minimum sum, not the actual elements used to make it. You can easily extend the idea to add that to your solution.