如何通过使用python添加来获取目标

Question

我有一个列表和一个目标编号。

• 我需要打印达到目标的方法数

l = [1,2,3]

target = 5

方式数如下

• 1+ 1 + 1 + 1 + 1 = 5
• 1 + 1 + 1+ 2 =5
• 1 + 2 + 2 = 5
• 1 +1 +3 =5
• 2 + 3 = 5

输出5方式

def countways(l, target ):

    if (target  == 0):
        return 0
    else:
        pass
if __name__ == "__main__":
     l = [1,2,3], 
     target = 5
     countways(l, target )

我们可以使用本机 python 或itertools?

Answer 1

我将假设所有数字都是正数。

您可以使用 itertools 来检查 all combinations_with_replacement，正如 Ann 所建议的那样，但是对于大输入，它会变得不必要地慢，因为有成倍数的组合。

朴素的递归方法

此版本使用 Nevetha 描述的递归方法，它允许提前返回永远找不到匹配项的分支，但应该进行替换。

与其他结果一样：扩展打印实际被加数相当容易。我们将简单地添加一个可选的第三个参数，该参数给出到目前为止的被加数，并将其打印在target == 0案例中。

def countWays(elements, target):
    if target < 0:
        return 0

    if target == 0:
        return 1

    total = 0
    for index, element in enumerate(elements):
       total += countWays(elements[index:], target - element)
 
    return total
 
 
if __name__ == '__main__':
    print(countWays([1, 2, 3], 5))
    print(countWays([5, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40], 30))
    print(countWays([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37], 40))
    print(countWays([1, 2, 3, 4, 5], 200))

DP算法

如您所见，对于 200 的目标，这已经需要相当长的时间来执行。这是因为在递归结束时，我们总是只向结果添加一个。这可以通过使用动态编程来改进——或者通过简单地添加缓存（示例代码，当然不应在任何实际程序中使用全局变量）：

cache = {}
def countWays(elements, target):
    global cache

    if target < 0:
        return 0

    if target == 0:
        return 1

    cache_key = (tuple(elements), target)
    if cache_key in cache:
        return cache[cache_key]

    total = 0
    for index, element in enumerate(elements):
       total += countWays(elements[index:], target - element)

    cache[cache_key] = total
    return total

或者直接构建 dp 数组，如这里已经讨论过的：

def countWays(elements, target):   
    dp = [1] + [0] * target
    for element in elements:
        for i in range(0, target - element + 1):
            dp[i + element] += dp[i]
    return dp[target]