def minCoinsToMakeChange(prices, X):
    # 初始化dp数组，初始值为X+1
    dp = [X + 1] * (X + 1)
    dp[0] = 0
    solution = [None] * (X + 1)

    for price in prices:
        for j in range(price, X + 1):
            if dp[j - price] + 1 < dp[j]:
                dp[j] = dp[j - price] + 1
                solution[j] = (price, j - price)

    # 回溯构建购买方案
    purchases = []
    remaining = X
    while remaining > 0:
        price, previous = solution[remaining]
        purchases.append(price)
        remaining = previous

    return dp[X], purchases

# 示例用法
prices = [8, 3, 5]
X = 28
min_count, purchase_list = minCoinsToMakeChange(prices, X)
print("购买方案:", purchase_list)  # 输出购买方案: [5, 2]


【 在 imchenghaibo 的大作中提到: 】
: 已知分别价值为a元b元c元d元e元的五种商品，现在手里边有现金n元，求怎么买这五种
: 商品才能使得花出去的钱无限接近于n元，但是又不超过n元。
: 想在网页上面用js脚本实现，但是目前看了别人几种算法不知道怎么改。
: 请教。
: ...................
--
FROM 119.139.197.*