Tutorvo
Menu
Courses Guides Pricing Log in Sign up

0/1 Knapsack: The Capacity × Item Grid, MAX(Skip, Take) and the Traceback

Lesson 5 of 818 minLab

This lesson is part of the course

In this lesson

You fill a 5-item × 11-capacity knapsack grid with MAX(skip, take), read off the best value for a 10 kg hamper and trace back which items were packed.

Buy the course once for $9.99 to unlock every lesson and lab, the final exam and the certificate – lifetime access, no subscription.

Buy course — $9.99 Log in

Lessons in this course

  1. Overlapping Subproblems: Counting the Calls of a Naive RecursionLab15 minFree
  2. Bottom-Up Tables: Ways to Climb n Stairs with 1-, 2- or 3-StepsLab14 min Locked
  3. Coin Change I: The Fewest Tokens for an Amount, Impossible Amounts & Why Greedy FailsLab16 min Locked
  4. Coin Change II: Counting the Ways Token by Token – and Why Loop Order MattersLab16 min Locked
  5. 0/1 Knapsack: The Capacity × Item Grid, MAX(Skip, Take) and the TracebackLab18 min Locked
  6. Longest Common Subsequence: Letters with MID, the LCS Grid and the TracebackLab17 min Locked
  7. Grid Paths & Cheapest Paths: Blocked Squares, Cost Grids and the Way BackLab17 min Locked
  8. Capstone: Longest Increasing Subsequence and Brute Force vs Dynamic ProgrammingLab18 min Locked