n əşya (hər birinin çəkisi və qiyməti var) və tutumu W olan çanta verilib. Hər əşyanı ən çox bir dəfə götürüb W-ni keçmədən ümumi qiyməti maksimuma çatdırmaq lazımdır. Qiymət/çəki nisbətinə görə aclıqlı üsul burada işləmir (aclıqlı alqoritmlər dərsindəki 160 və 220 nümunəsi), ona görə DP istifadə edirik.

Vəziyyət, keçid, baza, cavab

  • Vəziyyət: dp[i][w] — ilk i əşyadan istifadə edərək tutum w üçün ən yaxşı qiymət.
  • Keçid: i-ci əşyanı buraxırıq (dp[i-1][w]) və ya götürürük (dp[i-1][w-weight] + value, weight <= w olarsa) və maksimumu saxlayırıq.
  • Baza: dp[0][w] = 0.
  • Cavab: dp[n][W].
4 əşya və tutum 7 üçün bel çantası cədvəli
4 əşya və tutum 7 üçün bel çantası cədvəli

Cədvəl kodda

python
def knapsack(items, cap):
    n = len(items)
    # dp[i][w]: best value using the first i items with capacity w
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                       # skip item i
            if weight <= w:                               # or take it
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)
    return dp