البرمجة الديناميكية: الحالة والترتيب واستعادة الحل

from math import inf

def minimum_coins(coins, amount):
    if type(amount) is not int or amount < 0:
        raise ValueError("Amount must be a nonnegative integer")
    if any(type(coin) is not int or coin <= 0 for coin in coins):
        raise ValueError("Coins must be positive integers")
    best = [inf] * (amount + 1)
    parent = [None] * (amount + 1)
    best[0] = 0
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current and best[current - coin] + 1 < best[current]:
                best[current] = best[current - coin] + 1
                parent[current] = coin
    if best[amount] == inf:
        return None
    chosen, remaining = [], amount
    while remaining:
        coin = parent[remaining]
        chosen.append(coin)
        remaining -= coin
    return best[amount], chosen

print(minimum_coins([1, 3, 4], 6))
print(minimum_coins([4, 6], 5))
print(minimum_coins([1, 3], 0))

(2, [3, 3])
None
(0, [])

يُكوَّن المقدار 6 بالضبط باستخدام عملتين من فئة 3. ولا يمكن تكوين المقدار 5 من الفئتين 4 و6، بينما يملك الصفر الحل الفارغ.

def zero_one_knapsack(items, capacity):
    if type(capacity) is not int or capacity < 0:
        raise ValueError("Capacity must be a nonnegative integer")
    best = [0] * (capacity + 1)
    for weight, value in items:
        if type(weight) is not int or weight <= 0:
            raise ValueError("Weights must be positive integers")
        for current in range(capacity, weight - 1, -1):
            best[current] = max(best[current], best[current - weight] + value)
    return best[capacity]

print(zero_one_knapsack([(2, 3), (3, 4)], 4))
print(zero_one_knapsack([(2, 3)], 0))

4
0

لا يمكن استخدام العنصر ذي الوزن 2 مرتين. ويحافظ التكرار التنازلي على أن خلية المصدر تمثل طبقة العناصر السابقة.