时间戳

首页 > 解决方案 > 如何通过使用python添加来获取目标

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

问题描述

我有一份清单和一个目标号码。

l = [1,2,3]

target = 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？

标签： pythonadditertools

解决方案

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

您可以使用 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]

推荐阅读