如何通过使用 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

下面的作品

根据指定列表的元素计算目标的方法

def countWays(A, n, target):
 
    # base case: if a target is found
    if target == 0:
        return 1
 
    # base case: no elements are left
    if n < 0:
        return 0
 
    # 1. ignore the current element
    exclude = countWays(A, n - 1, target)
 
    # 2. Consider the current element
    #    2.1. Subtract the current element from the target
    #    2.2. Add the current element to the target
    include = countWays(A, n - 1, target - A[n]) + countWays(A, n - 1, target + A[n])
 
    # Return total count
    return exclude + include
 
 
if __name__ == '__main__':
 
    # input list and target number
    A = [5, 3, -6, 2]
    target = 6
 
    print(countWays(A, len(A) - 1, target), "ways")

Answer 2

可以使用itertools.combinations_with_replacement()方法：

from itertools import combinations_with_replacement as cwr

def countways(l, target):
    return len([1 for i in range(target) for j in cwr(l, i + 1) if sum(j) == target])

print(countways([1, 2, 3], 5))

输出：

说明

该方法的文档字符串如下：

Return r length subsequences of elements from the input iterable allowing individual elements to be repeated more than once.

所以和itertools.combinations()方法一样，期望itertools.combinations_with_replacement()方法允许元素重复。

如果您想可视化不同的解决方案：

from itertools import combinations_with_replacement as cwr

def countways(l, target):
    for i in range(target):
        for j in cwr(l, i + 1):
            if sum(j) == target:
                print(j)

countways([1, 2, 3], 5)

输出：

(2, 3)
(1, 1, 3)
(1, 2, 2)
(1, 1, 1, 2)
(1, 1, 1, 1, 1)

注意：正如@He3lixxx (+1) 所指出的，这对于大输入来说可能非常慢。可以通过过滤掉l中大于target的数字，将range(target)中的target除以max(l)和[=23来提高效率=]，像这样：

def countways(l, target):
    l = [i for i in l if i <= target]
    return len([1 for i in range(target // max(l) - 1,
                                 target // min(l)) for j in cwr(l, i + 1) if sum(j) == target])

Answer 3

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

您可以使用 itertools 检查所有 combinations_with_replacement，正如 Ann 所建议的，但是对于大输入，它会变得不必要地慢，因为组合呈指数级增长。

朴素的递归方法

此版本使用 Nevetha 描述的递归方法，它允许提前-return 离开永远找不到匹配项的分支，但应该通过替换来完成。

与其他结果一样：扩展以打印实际的加数相当容易。我们将简单地添加一个可选的第三个参数，该参数给出到目前为止的加数，并在 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 数组 here:

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]

Answer 4

动态规划方法将起作用。此代码输出所有可能的组合。只需打印列表的长度即可获得总计数。另外，所有可能的组合都是唯一的，不重复。

def ways(l, target):
    dp =[ [] for i in range(target+1) ]
    l.sort()
    n=len(l)
    for i in range(n):
        for j in range(l[i], target+1):    
            if j==l[i]:
                dp[j].append([l[i]])
            else:
                if dp[j-l[i]]:   
                    for u in dp[j-l[i]]:       
                        dp[j].append(u+[l[i]])       
    return dp[-1]

if __name__ == "__main__":
     l = [1,2,3] 
     target = 5
     print(len(ways(l, target)))
     l = [5, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
     target = 30
     print(len(ways(l, target)))

Answer 5

您可以使用 itertools 解决问题，如下例所示：

import itertools 

def countways(l, target): 
    data = []  
    for length in range(1, target+1):  
        data.extend([x for x in itertools.combinations_with_replacement(l, length) if sum(x) == target]) 
    return len(data)

您需要创建介于 1 和目标之间的所有尺寸的组合，因此 for 是必要的。在每次迭代中，您保存总和值等于 target 的组合。最后只需要统计保存的列表即可。

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

How to get the target by adding using python

python

add

itertools

朴素的递归方法

DP算法