Dynamic Programming Solution for a Variant of Coin Exchange

Question

I am practicing Dynamic Programming. I am focusing on the following variant of the coin exchange problem:

Let S = [1, 2, 6, 12, 24, 48, 60] be a constant set of integer coin denominations. Let n be a positive integer amount of money attainable via coins in S. Consider two persons A and B. In how many different ways can I split n among persons A and B so that each person gets the same amount of coins (disregarding the actual amount of money each gets)?

Example

n = 6 can be split into 4 different ways per person:

1. Person A gets {2, 2} and person B gets {1, 1}.
2. Person A gets {2, 1} and person B gets {2, 1}.
3. Person A gets {1, 1} and person B gets {2, 2}.
4. Person A gets {1, 1, 1} and person B gets {1, 1, 1}.

Notice that each way is non-redundant per person, i.e. we do not count both {2, 1} and {1, 2} as two different ways.

Previous research

I have studied at very similar DP problems, such as the coin exchange problem and the partition problem. In fact, there are questions in this site referring to almost the same problem:

• Dynamic Programming for a variant of the coin exchange - Here, OP studies the recursion relationship, but seems confused introducing the parity constraint.
• Coin Change :Dynamic Programming - Here, OP seems to pursue the reconstruction of the solution.
• Coin change(Dynamic programming) - Here, OP seems to also pursue the reconstruction of the solution.
• https://cs.stackexchange.com/questions/87230/dynamic-programming-for-a-variant-of-the-coin-exchange-problem - Here, OP seems to ask about a similar problem, yet parity, i.e. splitting into two persons, becomes the main issue.

I am interested mostly in the recursion relation that could help me solve this problem. Defining it will allow me to easily apply either a memoization of a tabulation approach to design an algorithm for this problem.

For example, this recursion:

def f(n, coins):
  if n < 0:
    return 0

  if n == 0:
    return 1

  return sum([f(n - coin, coins) for coin in coins])

Is tempting, yet it does not work, because when executed:

# => f(6, [1, 2, 6]) # 14

Here's an example of a run for S' = {1, 2, 6} and n = 6, in order to help me clarify the pattern (there might be errors):

Answer 1

This is what you can try:

Let C(n, k, S) be the number of distinct representations of an amount n using some k coins from S.

Then C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) The summation is for every s_i from S. S[i:] means all the elements from S starting from i-th element to the end - we need this to prevent repeated combinations.

The initial conditions are C(0, 0, _) = 1 and C(n, k, _) = 0 if n < 0 or k < 0 or n > 0 and k < 1 .

The number you want to calculate:

R = sum(C(i, k, S) * C(n - i, k, S)) for i = 1..n-1, k = 1..min(i, n-i)/Smin where Smin - the smallest coin denomination from S.

The value min(i, n-i)/Smin represents the maximum number of coins that is possible when partitioning the given sum. For example if the sum n = 20 and i = 8 (1st person gets $8, 2nd gets $12) and the minimum coin denomination is $2, the maximum possible number of coins is 8/2 = 4. You can't get $8 with >4 coins.

Answer 2

Here is a table implementation and a little elaboration on algrid's beautiful answer. This produces an answer for f(500, [1, 2, 6, 12, 24, 48, 60]) in about 2 seconds.

The simple declaration of C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) means adding all the ways to get to the current sum, n using k coins. Then if we split n into all ways it can be partitioned in two, we can just add all the ways each of those parts can be made from the same number, k, of coins.

The beauty of fixing the subset of coins we choose from to a diminishing list means that any arbitrary combination of coins will only be counted once - it will be counted in the calculation where the leftmost coin in the combination is the first coin in our diminishing subset (assuming we order them in the same way). For example, the arbitrary subset [6, 24, 48], taken from [1, 2, 6, 12, 24, 48, 60], would only be counted in the summation for the subset [6, 12, 24, 48, 60] since the next subset, [12, 24, 48, 60] would not include 6 and the previous subset [2, 6, 12, 24, 48, 60] has at least one 2 coin.

Python code (see it here; confirm here):

import time

def f(n, coins):
  t0 = time.time()

  min_coins = min(coins)

  m = [[[0] * len(coins) for k in xrange(n / min_coins + 1)] for _n in xrange(n + 1)]

  # Initialize base case
  for i in xrange(len(coins)):
    m[0][0][i] = 1

  for i in xrange(len(coins)):
    for _i in xrange(i + 1):
      for _n in xrange(coins[_i], n + 1):
        for k in xrange(1, _n / min_coins + 1):
          m[_n][k][i] += m[_n - coins[_i]][k - 1][_i]

  result = 0

  for a in xrange(1, n + 1):
    b = n - a

    for k in xrange(1, n / min_coins + 1):
      result = result + m[a][k][len(coins) - 1] * m[b][k][len(coins) - 1]

  total_time = time.time() - t0

  return (result, total_time)

print f(500, [1, 2, 6, 12, 24, 48, 60])