Change-making problem with specific constraints

I am a new Pythoner. I have solved a OJ project with Python. Can you tell me how can I solve it more Pythonically?

Problem Description: There are n coin denominations, each with an unlimited supply of coins. Use them to make a given total amount m.

Requirements:

• Every denomination must be used

• The number of coins of small denominations must be greater than the number of large denomination coins

• The total number of coins must be minimum

• If there is no combination of conditions to meet the conditions 1 and 2, the output "NA"

Input parameters:

• coin types n: 2

• The total amount m: m

• The largest denomination is less than 20

Program input: First line: the total amount requested Second row: each
coin denomination (in half-space separated)

Program output: First line: total number of coins Second row: the
number of small to large denomination of each coin (in half-space
separated)

Sample input:

20
1 2 5

Sample output:

9
4 3 2

#!/bin/bash/env python3
import copy

def coinChange():
    amount, coins = int(input()), list(sorted(map(int, input().split(sep=' '))))
    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  dp[last] + 1 and (j == 0 or package[j - 1] > package[j] + 1):
                    dp[i], package[j], packages[i] = dp[last] + 1, package[j] + 1, package
            else:
                break

    if dp[-1] > amount or packages[-1][-1] < 1:
        print('NA')
    else:
        print(sum(packages[-1]))
        print(' '.join([str(x) for x in packages[-1]]))

if __name__ == '__main__':
    coinChange()

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

StackExchange Code Review Q#138813, answer score: 11