Summary - Knapsack

Solve knapsack and print the best value in a mini task.

Summary - Knapsack

0/1 knapsack finds the max value with a 2D DP table and take/skip decisions. Used in resource allocation and investment decisions.

In this mini task you will solve knapsack and print the best value; combine all steps.

0/1 knapsack gives Θ(nW) time; if W is large it is called pseudo-polynomial.

Exercise Print knapsack

Write knap_print(W, weights, values, n). Print the max value with DP and print(). Output of knap_print(50, [10, 20, 30], [60, 100, 120], 3): 220.

Show example solution

def knap_print(W, weights, values, n):
    # Print knapsack
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    print(dp[n][W])
knap_print(50, [10, 20, 30], [60, 100, 120], 3)

Test yourself

Summary - Knapsack: match the terms

knapsack

Knapsack
DP

Table
take

Take
skip

Skip

Weight check

if weights[i - 1] <= ____:

Show answer

if weights[i - 1] <= w:

Knapsack is an example of which area?
- Backtracking
- Greedy
- Dynamic programming
- Divide and conquer
Show answer

Dynamic programming — Dynamic programming.

Next lesson: Project: Overview

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies