سير العمل البرمجي · قيمة حقيبة الظهر صفر-واحد

def knapsack_value(items, capacity):
    items = tuple(tuple(item) for item in items)
    if type(capacity) is not int or not 0 <= capacity <= 1000:
        raise ValueError("capacity.range")
    if len(items) > 64 or any(len(item) != 2 for item in items):
        raise ValueError("items.shape")
    if any(type(w) is not int or type(v) is not int or not 1 <= w <= 1000 or not 0 <= v <= 1000000 for w, v in items):
        raise ValueError("item.range")
    best = [0] * (capacity + 1)
    for weight, value in items:
        for limit in range(capacity, weight - 1, -1):
            best[limit] = max(best[limit], best[limit - weight] + value)
    return best[capacity]