algorithm - 实现 : Algorithm for a special distribution Problem

Question

我们有一个数字x，和一组面额为v₁的n硬币，< em>v₂, …, v_n.

硬币将在 Alice 和 Bob 之间分配，限制是每个人的硬币总和必须至少为 x。

例如，如果 x = 1，n = 2，并且 v₁ = v₂ = 2，则有两种可能的分布:一种是 Alice 得到硬币 #1，Bob 得到硬币 #2，另一种是相反。 (即使两种硬币面额相同，这些分布也被认为是不同的。)

我有兴趣计算可能的分布。我很确定这可以在 O(nx) 时间和 O(n+x) 空间使用动态规划；但我不知道该怎么做。

Answer 1

计算一个人得到刚好小于x的方法，将其加倍并从加倍的总方法数中减去将集合一分为二，(第二类斯特林数{n, 2})。

例如，

{2, 3, 3, 5}, x = 5

i  matrix
0  2: 1
1  3: 1 (adding to 2 is too much)
2  3: 2
3  N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8

下面的 Python 代码使用了 MBo 的例程。如果您喜欢这个答案，请考虑对该答案投赞成票。

# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
  n1=n
  k1=k
  if n<=0:
    return 1
  elif k<=0:
    return 0   
  elif (n==0 and k==0):
    return -1
  elif n!=0 and n==k:
    return 1
  elif n<k:
    return 0
  else:
    temp1=stirling(n1-1,k1)
    temp1=k1*temp1
    return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
  a = [1] + (x-1) * [0]

  # Code by MBo
  # https://stackoverflow.com/a/53418438/2034787
  for c in coins:
      for i in xrange(x - 1, c - 1, -1):
          if a[i - c] > 0:
              a[i] = a[i] + a[i - c]

  return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16