1. Review
The function coinChange carries out three tasks: (i) read the input; (ii) solve the problem; (iii) print the solution. This makes it hard to test, because it's hard to run the code on different problem instances (you have to feed it the problem in text form on standard input), and becaue it's hard to automatically check the output (you have to capture the standard output).
It would be easier to test the code if task (ii) were refactored into a separate function. I'd write something like this:
class NoSolution(Exception):
pass
def coin_change(amount, coins):
"""Given a target amount and a sorted list of coins denominations,
determine how to make change for amount with the minimum number of
coins, subject to the restrictions that every denomination is used
and the number of coins of a small denomination must be greater
than the number of coins of a large denomination. Return a list
giving the number of coins of each denomination, or raise
NoSolution if making change is impossible under the constraints.
"""
# ... see below ...
def main():
"""Read coin change problem from standard input and write solution to
standard output, or NA if there is no solution.
"""
amount, coins = int(input()), list(sorted(map(int, input().split())))
try:
result = coin_change(amount, coins)
except NoSolution:
print('NA')
else:
print(sum(result))
print(*result)
and now it's easy to test the code, for example from the interactive interpreter:
>>> coin_change(20, [1, 2, 5])
[4, 3, 2]
sorted already returns a list, so there is no need to pass the result to list.
str.split splits on whitespace by default, so there is no need to pass sep=' ' in this case.
Note in the code above that I handle an exceptional result by raising an exception (instead of returning some exceptional value). This is more robust because it is easy to forget to check the result of a function, causing exceptional cases to be silently mishandled.
These lines are unnecessary:
min_package = [x for x in range(len(coins), 0, -1)]
min_sum = sum(map(lambda x, y:x * y, min_package , coins))
if amount < min_sum:
print('NA')
return
That's because there is already logic for detecting unsolvable problem instances later in the function. There's no point in doing this twice: duplicate code has twice the opportunties for bugs.
The line:
dp, dp[0] = [amount + 1] * (amount + 1), 0
is kind of tricksy (the reader would need to be very sure of Python's order-of-evaluation rules to know that dp[0] is evaluated after dp is assigned), and so it would be simpler to write something like:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
or alternatively,
dp = [0] + [amount + 1] * amount
The only role of amount + 1 in this line is to be greater than every possible number of coins. I think it would be clearer to use a value like float('inf') here.
This loop:
for i in range(len(dp)):
would be better written like this:
for i in range(1, amount + 1):
This is because there's no point in considering making change for 0, so we might as well start at 1, and because amount + 1 makes it clear that we consider all values up to amount, without having to remember how many elements there are in the list dp.
In Python we prefer not to use tuple assignment just to save on lines of code (only when we really do have a tuple to assign). This kind of code is hard to follow:
dp[i], package[j], packages[i] = dp[last] + 1, package[j] + 1, package
because you have to count carefully to see which expression on the right is assigned to which expression on the left. I think it's clearer to write:
dp[i] = dp[last] + 1
package[j] += 1
packages[i] = package
Notice that I can use the += operator here, which wasn't possible in the tuple assignment version of the code.
Making a deep copy of packages[last] is unecessary: this is a list of integers, and so a shallow copy would work.
There's no need to import the copy module just to take a shallow copy of a list. It's simpler to use the built-in function list.
The code takes a copy of packages[last] before testing whether coin could be used. But this is a waste if coin in fact cannot be used. It would be better to take the copy after the test, like this:
package = packages[last]
if dp[i] > dp[last] + 1 and (j == 0 or package[j - 1] > package[j] + 1):
dp[i] = dp[last] + 1
new_package = list(package)
new_package[j] += 1
packages[i] = new_package
The meaning of the name dp is not clear to me. The value dp[i] is the smallest number of coins found so far that makes change for i under the restrictions of the problem. Even knowing this, I can't work out what "dp" stands for! I would use a name like min_coins together with a comment explaining the meaning.
Update: does "dp" stand for "dynamic programming"??
The meaning of the name package is also not clear. The value packages[i][j] is the number of coins of the j'th denomination in the best solution found so far that makes change for i under the restrictions of the problem. So I'd use a name like solutions together with a comment.
Instead of:
if coin <= i:
# ...
else:
break
I would write:
if coin > i:
break
# ...
which saves a level of indentation. In general, it's a good idea to dispose of exceptional cases first.
At the end of the function, the code uses packages[-1] to get the solution for amount. It would be clearer to write packages[amount]. Then the reader wouldn't have to remember how many elements there are in the list packages.
In the line:
if dp[-1] > amount or packages[-1][-1] < 1:
the first part of the condition (dp[-1] > amount) is unnecessary; the second part of the condition suffices.
2. Revised code
def coin_change(amount, coins):
"""Given a target amount and a sorted list of coins denominations,
determine how to make change for amount with the minimum number of
coins, subject to the restrictions that every denomination is used
and the number of coins of a small denomination must be greater
than the number of coins of a large denomination. Return a list
giving the number of coins of each denomination, or raise
NoSolution if making change is impossible under the constraints.
"""
# min_coins[i] is smallest number of coins found making change for i.
min_coins = [0] + [float('inf')] * amount
# solutions[i][j] is the number of coins of the j'th denomination in
# the best solution found making change for i.
solutions = [[0] * len(coins)] * (amount + 1)
for i in range(1, amount + 1):
for j, coin in enumerate(coins):
if coin > i:
break
last = i - coin
solution = solutions[last]
if (min_coins[i] > min_coins[last] + 1
and (j == 0 or solution[j - 1] > solution[j] + 1)):
min_coins[i] = min_coins[last] + 1
new_solution = list(solution)
new_solution[j] += 1
solutions[i] = new_solution
if solutions[amount][-1] == 0:
raise NoSolution()
else:
return solutions[amount]
3. Improved algorithm
The data structure packages ends up containing len(coins) * (amount + 1) values. But this is a waste of memory and computation, because you ought to be able to describe each solution by giving only the denomination of the highest coin used in that solution. Then you could subtract that coin and look up the remainder to get the next coin, and so on.
But if you try to implement this then you'll struggle, because in the revised data structure you can't apply the restriction that every denomination is used and the number of coins of a small denomination must be greater than the number of coins of a large denomination.
However, there's a way to transform the problem so that it turns into an ordinary (unrestricted) change-making problem. The idea is that if you're given the problem instance:
make change for 20 using fewest coins with values 1, 2, 5 (with the restriction)
then you transform it into:
make change for 8 using fewest coins with values 1, 3, 8 (without the restriction)
which has the solution 0, 0, 1 which transforms into the solution 4, 3, 2 in the original problem.
No doubt you're asking, what is this transformation and how does it work? There are two steps in the transformation:
Any solution has to contain at least one of the highest denomination of coin (because all denominations have to be included), at least two of the second highest denomination (because the number of coins of a small denomination must be greater than the number of coins of a large denomination), at least three of the third highest denomination, and so on. So we can start by subtracting all these coins from the amount, and then drop the restriction that all denominations have to be included.
In the example above, we know that the solution has to include at least 3×1, 2×2 and 1×5, so we start by subtracting 12 from the amount, getting 8.
Now, whenever we add a coin of some denomination to the solution we're building up, we have to add coins of all smaller denominations too, to maintain the restriction that number of coins of a small denomination must be greater than the number of coins of a large denomination. So if we add a coin of denomination 2, then we have to add a coin of denomination 1 too. And if we add a 5, we have to add 2 and 1 too.
But if a 2 always has to be accompanied by a 1, this is almost the same as having a coin of denomination 3. And if 5 always has to be accompanied by a 2 and a 1, this is almost the same as having a coin of denomination 8. So we can transform the problem into one where the coins have values 1, 3, and 8, and then drop the restriction that number of coins of a small denomination must be greater than the number of coins of a large denomination.
I wrote "almost the same" above because there is a difference in how we have to count the number of coins in order to ensure we meet the "minimum number of coins" condition. See the line marked "(A)" in the code below.
In the transformed problem we can represent the solutions more compactly as discussed above, and then reconstruct the full solution coin by coin at the end. Here's an implementation.
from itertools import accumulate
def coin_change(amount, coins):
"""Given a target amount and a sorted list of coins denominations,
determine how to make change for amount with the minimum number of
coins, subject to the restrictions that every denomination is used
and the number of coins of a small denomination must be greater
than the number of coins of a large denomination. Return a list
giving the number of coins of each denomination, or raise
NoSolution if making change is impossible under the constraints.
"""
# Transform problem into (almost) standard change-making problem.
coins = list(accumulate(coins)) # see (2) above
amount -= sum(coins) # see (1) above
if amount < 0:
raise NoSolution()
# min_coins[i] is smallest number of coins found making change for i.
min_coins = [0] + [float('inf')] * amount
# solutions[i] is the index of the highest coin in the best
# solution found making change for i, or -1 if no solution has
# been found.
solutions = [-1] * (amount + 1)
# Solve the transformed problem
for i in range(1, amount + 1):
for j, coin in enumerate(coins):
if coin > i:
break
last = i - coin
new_coins = min_coins[last] + j + 1 # (A)
if min_coins[i] > new_coins:
min_coins[i] = new_coins
solutions[i] = j
# Reconstruct solution in the transformed problem.
result = [0] * len(coins)
while True:
j = solutions[amount]
if j == -1:
break
result[j] += 1
amount -= coins[j]
if amount != 0:
raise NoSolution()
# Transform solution back again.
return list(accumulate(r + 1 for r in reversed(result)))[::-1]
