具有最小元素的子集和

Question

给定一个排序的整数列表，始终包含 1。使用最少数量的元素找到一个目标值，并求和到目标值。所有数字都可以使用多个。

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)

我知道我们应该检查我们是否使用一个元素达到其最大数量来填充目标值但是我很困惑一旦我们有了正确的递归就如何正确计算使用的元素数量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()

我的基本情况不正确吗？既然我想要最小的错误大小写应该 return 1？还是我调用递归的时候出错了？

Answer 1

我认为代码试图解决与标题中描述的问题不同的问题。您似乎在计算使用 X 中的面额找零金额 t 的不同方法的数量。这是执行此操作的代码版本：

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}]

为了找到达到金额t所需的最少硬币数量，您需要修改您的归纳步骤。而不是为 t 的较小值添加金额，您需要取最小值：

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

具有最小元素的子集和

Subset sum with minimum elements

python

recursion

backtracking