Subset sum with minimum elements-CodePudding

Given a sorted list of integers, always containing 1. Find a target value using the minimum amount of elements to sum to the target value. All numbers can be used more than one.

e.x. {1,9,10} Target = 18, solution is 2 elements (9 twice).
{1,3,5,7} Target = 15, solution is 3 elements (7,7,1 or 5,5,5)

I understand that we should check whether we use an element up to its maximum amount to fill the target value but I am confused on how to correctly count the number of elements used once we have a correct recursive return.

def main():
    sections = list(map(int,input().split(" ")))
    
    t = int(input())

    print((subset_sum(sections,len(sections)-1,t)), "elements minimum")

def subset_sum(X, i, t):
    count = 0
    if t == 0:
        return 1
    if t < 0 or abs(i) == len(X):
        return 0

    for z in range(0,t//X[i]):
        count  = subset_sum(X,i-1,t-(z*X[i]))

    return count

if __name__ == "__main__":
    main()

Is my base case incorrect? Since I want the minimum should the incorrect case return 1? Or do I have a mistake when I call the recursion?

CodePudding user response：

I think the code is trying to solve a different problem than the one described in the title. You seem to be counting the number of different ways to make change for amount t using denominations in X. Here is a version of your code that does this:

def subset_sum(X, i, t):
    count = 0
    if t == 0:
        return 1
    if t < 0 or i < 0:
        return 0

    for z in range(0,t//X[i]   1):
        count  = subset_sum(X,i-1,t-(z*X[i]))

    return count

subset_sum([5, 2, 1], 2, 30) # 58 ways to make change
# same as the following Mathematica code:
# Length@IntegerPartitions[30, All, {1, 2, 5}]

In order to find the minimum number of coins needed to achieve amount t, you need to modify your inductive step. Instead of adding the amounts for smaller values of t, you need to take the minimum:

from functools import lru_cache

def coin_change(denominations, target):
  'Return minimum number of coins with given denominations to make a target sum'
  @lru_cache(None)
  def f(target):
    if target == 0:
      return 0
    elif target < 0:
      return float("inf")
    return min(f(target - d) for d in denominations)   1
  return f(target)

coin_change([1, 2, 5], 30) # minimum number of coins is 6