Δυναμικός προγραμματισμός — ελάχιστα κέρματα και μη προσβάσιμες καταστάσεις

Το πρόβλημα

Ένα μικρό τοπικό εργαλείο πρέπει να βρει τον ελάχιστο αριθμό κερμάτων για συγκεκριμένο ποσό. Η άπληστη επιλογή του μεγαλύτερου κέρματος δεν είναι πάντοτε σωστή: με αξίες 1, 3 και 4, το ποσό 6 γίνεται καλύτερα με 3+3 (δύο κέρματα) παρά με 4+1+1 (τρία). Στον δυναμικό προγραμματισμό αξιοποιούμε αποτελέσματα μικρότερων ποσών. Το dp[x] περιέχει τον ελάχιστο αριθμό κερμάτων που παράγουν ακριβώς το x, ενώ η None σημαίνει ότι το ποσό είναι αδύνατο.

Εκτελέσιμο πρόγραμμα Python 3

Αποθήκευσε ως coin_dp_lab.py και εκτέλεσε python3 coin_dp_lab.py. Το ποσό περιορίζεται στις 10.000 μονάδες, ώστε μη έμπιστη είσοδος να μη δεσμεύει ανεξέλεγκτη μνήμη. Μηδενικές ή αρνητικές αξίες κερμάτων απορρίπτονται.

def min_coins(amount, denoms):
    if type(amount) is not int or not 0 <= amount <= 10000:
        raise ValueError("amount outside bounded lab")
    if not denoms or any(type(c) is not int or c <= 0 for c in denoms):
        raise ValueError("invalid denominations")
    dp = [None] * (amount + 1)
    dp[0] = 0
    for value in range(1, amount + 1):
        options = [dp[value-c] + 1 for c in denoms
                   if c <= value and dp[value-c] is not None]
        dp[value] = min(options) if options else None
    return dp[amount]

assert min_coins(6,(1,3,4)) == 2
assert min_coins(3,(2,)) is None
assert min_coins(0,(2,)) == 0
try:
    min_coins(10,(0,))
except ValueError:
    pass
else:
    raise AssertionError("zero coin accepted")
print("PASS: optimal count and unreachable amounts")

Μετάβαση κατάστασης και εξήγηση

Η βάση dp[0]=0 περιγράφει την κατασκευή μηδενικού ποσού χωρίς κέρματα. Για κάθε ποσό x από 1 έως τον στόχο εξετάζουμε κάθε κέρμα c που δεν ξεπερνά το x. Αν το dp[x-c] είναι προσβάσιμο, η τιμή dp[x-c]+1 αντιστοιχεί σε λύση που τελειώνει με το κέρμα c. Το ελάχιστο όλων των τέτοιων λύσεων δεν μπορεί να αποκλείσει τη βέλτιστη, γιατί κάθε λύση έχει κάποιο τελευταίο κέρμα. Ο χρόνος είναι O(ποσό × πλήθος_αξιών) και η μνήμη O(ποσό).

Μικρές ασκήσεις και έλεγχοι

1. Αποθήκευσε ποιο κέρμα οδήγησε σε κάθε βέλτιστη κατάσταση και ανακατασκεύασε την πλήρη λύση.
2. Αφαίρεσε την αξία 1 και ζήτησε ποσό που δεν μπορεί να κατασκευαστεί. Εξήγησε γιατί None δεν ισοδυναμεί με μηδέν.
3. Υλοποίησε άπληστη επιλογή και χρησιμοποίησε το 6 με κέρματα 1/3/4 ως συγκεκριμένο αντιπαράδειγμα.
4. Σύγκρινε αναδρομική απομνημόνευση με επαναληπτικό πίνακα για ποσά έως 1000 και σημείωσε βάθος αναδρομής.

Παραδοτέα: PASS, πίνακας καταστάσεων από 0 έως 6, μία αδύνατη περίπτωση και τεκμηρίωση κόστους.