Subset sum with minimum elements

Question

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?

hilberts_drinking_problem · Accepted Answer · 2022-02-16 23:02:09Z

1

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

answered Feb 16, 2022 at 23:02

hilberts_drinking_problem

11.6k3 gold badges25 silver badges55 bronze badges

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

4 Comments

ShrooMsss Over a year ago

Ah, I understand now, I am still very new to python. So your solution to the real problem uses Dynamic programming correct? If possible could you elaborate on it as it still confuses me. Thank You though!

hilberts_drinking_problem Over a year ago

Yes, both solutions usually use dynamic programming, although the first one does not with the current implementation. The idea is to note that if you can make amount t - X[i] with n coins, you can make the amount t with n + 1 coins. Since no number of coins can make a negative amount, the corresponding base case return infinity.

ShrooMsss Over a year ago

Thank you for answering that question it makes sense, my last question is it possible to have an okay runtime solution not using dynamic programming? Or would those possibilities take almost forever?

hilberts_drinking_problem Over a year ago

I am not aware of any non-DP solutions for the problem of finding the smallest number of coins with a given sum. For the other problem (counting the number of ways to make change), there is a cool math approach using generating functions, although dynamic programming might be needed to implement it efficiently anyhow.

Collectives™ on Stack Overflow

Subset sum with minimum elements

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related