题解 | #自动售货系统# #动态规划# 最折磨的一集

import sys
from dataclasses import dataclass
from typing import List


@dataclass
class Goods:
    name: str
    price: int
    quantity: int


coins = (1, 2, 5, 10)


class Machine:
    def __init__(self):
        self.goods: List[Goods] = [Goods(f"A{x}", x + 1, 0) for x in range(1, 5)] + [
            Goods("A5", 8, 0),
            Goods("A6", 6, 0),
        ]
        self.coin_box: List[int] = []
        self.balance: int = 0

    def init(self, goods_quantity: List[int], coins_qunatity: List[int]) -> str:
        for good, qty in zip(self.goods, goods_quantity):
            good.quantity = qty
        for index, qty in enumerate(coins_qunatity):
            self.coin_box += [coins[index]] * qty
        return "S001:Initialization is successful"

    def is_sold_out(self) -> bool:
        # 如果卖完就返回true
        return all(good.quantity == 0 for good in self.goods)

    def sum_of_one_two(self) -> int:
        return self.coin_box.count(1) + 2*self.coin_box.count(2)

    def insert_coin(self, amount: int) -> str:
        if amount not in {1, 2, 5, 10}:  # 不为指定面额
            return "E002:Denomination error"
        if self.sum_of_one_two() < amount:
            return "E003:Change is not enough, pay fail"
        if self.is_sold_out():  # 卖完
            return "E005:All the goods sold out"
        self.balance += amount
        self.coin_box.append(amount)
        return f"S002:Pay success,balance={self.balance}"

    def purchase(self, good: str) -> str:
        for x in self.goods:
            if x.name == good:
                if x.quantity == 0:  # 数量为0
                    return "E007:The goods sold out"
                if self.balance < x.price:  # 钱不够
                    return "E008:Lack of balance"
                # 购买商品成功后，自动售货机中对应商品数量减1，投币余额扣除本次购买商品的价格。
                x.quantity -= 1
                self.balance -= x.price
                return f"S003:Buy success,balance={self.balance}"
        return "E006:Goods does not exist"

    def return_cash(self) -> str:
        if self.balance == 0:
            return "E009:Work failure"
        # 按钱币总张数最少的原则进行退币
        # 如果因零钱不足导致不能退币，则尽最大可能退币

        tmp = [()] * (self.balance+1)
        self.coin_box = sorted(self.coin_box, reverse=True)
        for x in self.coin_box:
            for index, comb in enumerate(tmp):
                if comb == () and index != 0:
                    continue
                new_amount = index + x
                if new_amount > self.balance:
                    continue

                if tmp[new_amount] != ():
                    if len(tmp[new_amount]) > len(comb) + 1:
                        tmp[new_amount] = tuple(comb) + (x,)
                else:
                    tmp[new_amount] = tuple(comb) + (x,)
       
        for x in reversed(tmp):
            if x != ():
                # 从零钱中删除该组合
                # 清零balance
                
                for y in x:
                    self.coin_box.remove(y)
                self.balance = 0
                return self.return_coins_str(x)

    def return_goods_str(self):
        return "\n".join(f"{x.name} {x.price} {x.quantity}" for x in self.goods)

    def return_coins_str(self,coin):
        return '\n'.join(f"{x} yuan coin number={coin.count(x)}" for x in coins)

    def return_self_coins_str(self):
        return self.return_coins_str(self.coin_box)

def solve_cmd(cmd: str, machine: Machine):
    #分析解后的命令 例如 p 1
    content = cmd.split()
    result  = 'E010:Parameter error'
    if len(content) == 1 and content[0] == 'c':
        result = machine.return_cash()

    if content[0] == 'r':
        result = machine.init(list(map(int,content[1].split('-'))), list(map(int,content[2].split('-'))))

    if content[0]=='p':
        result = machine.insert_coin(int(content[1]))

    if content[0]=='b':
        result = machine.purchase(content[1])

    if content[0]=='q':
        if content[1] == '0':
            result = machine.return_goods_str()
        elif content[1] == '0':
            result = machine.return_goods_str()
            
    return result

machine = Machine()
command = input().split(';')
for x in command:
    if x:
        print(solve_cmd(x,machine))

需要用动态规划计算每个数值的最小可能组合，最好是逆序从最大的面值开始找起，为以防找不到组合，把动态规划的列表进行一个逆序输出。输出答案的时候不要忘记把余额清零，零钱也不要忘去除。

最折磨的苦力题目