总和整数与restrictrions

Question

获取权的问题的要点：

In how many ways can we add k positive integers to reach a sum of exactly n if each number is smaller or equal to given number m?

的问题是可以解决的动态编程，但我坚持，因为我无法找到解决方案的最优子或递归。

Answer 1

下面是Python 3中一个简单的函数，它应该适合您的描述。我假设0不是一个可接受的值，但它是一个微不足道的变化。

def howMany(k, n, m): 

    def sub(pos, currentSum, path): 
     if currentSum == n and pos == k: # reached the sum, print result and increase counter by 1 
      print(path) 
      return 1 
     elif currentSum < n and pos < k: # still worth trying 
      count = 0 
      for i in range(1, m): 
       count += sub(pos + 1, currentSum + i, path+[i]) 
      return count 
     else: # abort 
      return 0 

    return sub(0, 0, []) 

print(howMany(3, 10, 6)) 

产生

[1, 4, 5] 
[1, 5, 4] 
[2, 3, 5] 
[2, 4, 4] 
[2, 5, 3] 
[3, 2, 5] 
[3, 3, 4] 
[3, 4, 3] 
[3, 5, 2] 
[4, 1, 5] 
[4, 2, 4] 
[4, 3, 3] 
[4, 4, 2] 
[4, 5, 1] 
[5, 1, 4] 
[5, 2, 3] 
[5, 3, 2] 
[5, 4, 1] 
18 

它可以被优化，但会在此阶段模糊逻辑。