Skills101
← All practice quizzes

Quiz: 0/1 Knapsack and Subset Sum

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

The classic "pick items under a weight limit" problem, solved with a 2D table and then a 1D array. Learn why greedy fails, why the loop must run backwards, and how subset sum and equal partition use the same idea.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    Why does greedy by value per kg fail for 0/1 knapsack?

  2. Question 2

    In the 2D table, what does dp[i][c] mean?

  3. Question 3

    What does this print?

    wt, val, W = [2, 3, 4], [3, 4, 6], 5
    dp = [0] * (W + 1)
    for w, v in zip(wt, val):
        for c in range(W, w - 1, -1):
            dp[c] = max(dp[c], v + dp[c - w])
    print(dp[W])
    
  4. Question 4

    In the 1D 0/1 knapsack, why must c go from high to low?

  5. Question 5

    What does this print?

    dp = [0] * 7
    for c in range(2, 7):
        dp[c] = max(dp[c], 5 + dp[c - 2])
    print(dp[6])
    
🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →