代码优化 - 组合数量

有一个C给定的数（C是一个整数），并给出了一个数字列表（我们称之为N，列表N中的所有数字都是整数）。我的任务是找到的可能性来表示C.代码优化 - 组合数量

例如量：

输入：

C = 4 

N = [1, 2]

输出：

因为：

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2

我的代码对于小数字来说工作得很好。然而，我不知道如何优化它，所以它也可以用于更大的整数。任何帮助将不胜感激！

有我的代码：

import numpy 
import itertools 
def amount(C): 
    N = numpy.array(input().strip().split(" "),int) 
    N = list(N) 
    N = sorted(N) 
    while C < max(N): 
     N.remove(max(N)) 
    res = [] 
    for i in range(1, C): 
     for j in list(itertools.combinations_with_replacement(N, i)): 
      res.append(sum(list(j))) 
    m = 0 
    for z in range (0, len(res)): 
     if res[z] == C: 
      m += 1 
    if N[0] == 1: 
     return m + 1 
    else: 
     return m

来源

2016-12-27 Hendrra

这里真的不需要numpy。如果有的话，它会放慢你的速度。无论如何，你立即把它变成一个“列表”。这是没有意义的。 –

您似乎想要对分区进行计数：请参阅https://en.wikipedia.org/wiki/Partition_(number_theory）。 –

您可以在http://docs.sympy.org/dev/_modules/sympy/ntheory/partitions_.html中将您的代码与npartitions进行基准测试。 –

算法的复杂性为O(len(a)^С)。为了更有效地解决这个问题，请使用dynamic programming的想法。

假设dp[i][j]等于分区数i使用条款a[0], a[1], ..., a[j]。阵列a不应包含重复项。此解决方案运行时间为O(C * len(a)^2)。

def amount(c): 
    a = list(set(map(int, input().split()))) 

    dp = [[0 for _ in range(len(a))] for __ in range(c + 1)] 
    dp[0][0] = 1 

    for i in range(c): 
     for j in range(len(a)): 
      for k in range(j, len(a)): 
       if i + a[k] <= c: 
        dp[i + a[k]][k] += dp[i][j] 

    return sum(dp[c])

来源

2016-12-27 23:53:44 Andreikkaa

运行速度非常快！谢谢您的帮助。 – Hendrra

就是这样 - 我的数组包含了很多重复项。你能解释一下最后的“if”是如何工作的吗？ – Hendrra

@ Hendrra这是一种边界检查。这个'if'语句根本不影响解决方案。 – Andreikkaa

请这首：https://en.wikipedia.org/wiki/Combinatorics
也是这个https://en.wikipedia.org/wiki/Number_theory
如果我是你，我会分裂的C上的N [1]第一，检查C不是原始数从你的例子：4/1 = [4] =>整数计数1
4/2 = [2] =>整数计数器变成2，然后做分割[2]为1 + 1如果1在集合中
如果集合中有3个[1,2,3 ]，4/3只需要减去4-3 = 1，如果1在集合中，则计数器增加，对于更大的结果，我将根据集合进行一些分区。

来源

2016-12-27 23:17:01

感谢所有的链接和一个新的想法。这是一个很好的解决方案（它显示了很多数学）！我也会考虑的。不过，我认为它可能会比上面的慢一点。 – Hendrra

代码优化 - 组合数量

回答

相关问题