0/1 Knapsack: Take or Leave
Maximize value under a weight cap.
0/1 Knapsack: Take or Leave is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Knapsack Story
You have a bag with a weight limit and a pile of items. The 0/1 knapsack asks: which items maximize value without overpacking? 🎒
Take or Leave
The word 0/1 means each item is either fully taken or fully skipped. You can never grab half an item, so every choice is yes or no.
Why Greedy Fails
Grabbing the cheapest or most valuable item first can waste capacity. The greedy shortcut breaks here, so you need to consider real combinations.
The Two Inputs
You are given two parallel lists: a weight and a value for each item, plus one capacity. Item i has weight wt[i] and value val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Define the State
Let dp[i][w] be the best value using the first i items with capacity w. Naming the state precisely is the whole game.
The Skip Choice
If you skip item i, your value is whatever you already had: dp[i-1][w]. The capacity stays untouched for the rest.
The Take Choice
If you take item i, add its value and shrink capacity: val[i] + dp[i-1][w - wt[i]]. This is only legal when w is at least wt[i].
Pick the Better Branch
The recurrence simply keeps the larger of the two options with max. Each cell trusts the answers already computed below it.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])The Base Row
With zero items you can carry zero value at any capacity. That base case fills the first row with all zeros to build on.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Fill the Table
Loop items in the outer pass and capacities in the inner pass. Each cell reads only the row above, so a single sweep fills everything.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Read the Answer
The bottom-right cell dp[n][cap] holds the maximum value for all items and full capacity. That single cell is your final answer.
Quick Check
Test the core 0/1 knapsack recurrence.
Recap
You learned 0/1 knapsack: each item is take-or-leave, dp[i][w] keeps the best of skip versus take, and dp[n][cap] is the answer. 🎉
Frequently asked questions
Is the “0/1 Knapsack: Take or Leave” lesson free?
Yes — the full text of “0/1 Knapsack: Take or Leave” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “0/1 Knapsack: Take or Leave”?
Maximize value under a weight cap. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “0/1 Knapsack: Take or Leave” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- 0/1 Knapsack: Take or Leave
- Space-Optimized Knapsack
- Unbounded & Coin-Change DP
- Subset Sum & Partition