Understanding 0/1 Knapsack in the Easiest Way Possible (Recursion + Memoization)

If you are learning Dynamic Programming, chances are you have heard about the famous 0/1 Knapsack Problem. And chances are even higher that it looked confusing at first.

But honestly, 0/1 Knapsack is much simpler than people make it look.

By the end of this article, you will understand:

• what the problem really means
• why recursion works
• what n actually represents
• how subsets are explored
• why memoization is needed
• what gets stored in the DP table
• and how to think about the problem naturally

Let’s begin.

What is the 0/1 Knapsack Problem?

Suppose you have:

• a bag with limited capacity
• some objects
• every object has a weight and a profit value

Your goal is:* Choose some objects such that*:

• total weight does not exceed the bag capacity
• total profit becomes maximum

For example Value = {3, 12, 7, 9, 6} Weight = {2, 4, 3, 5, 2} Capacity = 8

Now we need to choose some objects.

But we cannot exceed weight 8.

And among all valid combinations, we want the one with maximum profit.

Why is it called 0/1 Knapsack?

Because for every object:

• either we take it (1)
• or we do not take it (0)

We cannot take an object multiple times.

So every object has only 2 choices:

take it don’t take it

And that is the entire core idea of the problem.

The Real Intuition Behind Knapsack

Most people think knapsack is some special difficult DP problem.

But actually:

Knapsack is just a choose / not choose problem with a weight constraint attached to it.

For every object:

• choose it
• or don’t choose it

This naturally creates subsets/combinations.

Think Like This

Imagine you have toys.

Every toy:

• has weight
• gives happiness (profit)

You have a small bag.

Now for every toy, you ask:

Should I take this toy? OR Should I leave it?

If the toy is too heavy:

I cannot take it.

Recursive Thinking

Now let’s understand recursion properly.

Suppose:

val = {3, 12, 7, 9, 6}

Number of objects:

n = 5

What Does n Represent?

This confuses almost everyone initially.

Many beginners think:

n = index

But that is not fully correct.

The correct meaning is:

n represents how many objects we are currently allowed to consider.

So:

| n | Objects we can consider |
| - | ----------------------- |
| 5 | {3,12,7,9,6}            |
| 4 | {3,12,7,9}              |
| 3 | {3,12,7}                |
| 2 | {3,12}                  |
| 1 | {3}                     |
| 0 | no objects              |

Then Why Do We Use (n-1)?

Because arrays are 0-indexed.

So:

• if n = 5
• last object index = 4

That is:

val[n-1] wt[n-1]

Very Important Understanding

At every recursive call:

We make decision for only ONE object.

Not all objects together.

Specifically:

the last object among current n objects

So:

• n = 5 → decide for object 4
• n = 4 → decide for object 3
• n = 3 → decide for object 2

and so on.

The Two Choices

For every object:

Choice 1: Pick it

Only possible if:

wt[n-1] <= W

Then:

• add its profit
• reduce capacity
• solve remaining problem

Choice 2: Don’t Pick it

Simply skip the object.

This Creates a Recursive Tree

Every object creates 2 branches:

pick not pick

Then again:

pick not pick

and so on.

So recursion explores all possible combinations/subsets implicitly.

Important Clarification

We do NOT:

1. first generate all subsets
2. then compare them later

Instead:

recursion explores subsets while simultaneously calculating the answer.

Recursive Tree Example

Let’s simplify:

val = {3, 12, 7}

Recursive structure becomes:

                           {}
                        Decide 7
                      /            \
                pick                not pick
                 {7}                   {}
               /      \             /      \
         pick 12    not 12     pick 12   not 12
          {7,12}      {7}        {12}        {}
          /   \       /  \       /   \       /  \
     {7,12,3} {7,12} {7,3} {7} {12,3} {12} {3} {}

Base Case

Eventually:

n == 0

meaning: No objects left.

or:

W == 0

meaning: No capacity left.

So answer becomes: 0

Recursive Code

#include <bits/stdc++.h>
using namespace std;

int knapsackRec(int W, vector<int> &val, vector<int> &wt, int n) {

    // Base case
    if (n == 0 || W == 0)
        return 0;

    int pick = 0;

    // Pick the object
    if (wt[n - 1] <= W)
        pick = val[n - 1] +
               knapsackRec(W - wt[n - 1], val, wt, n - 1);

    // Don't pick the object
    int notPick = knapsackRec(W, val, wt, n - 1);

    // Return maximum
    return max(pick, notPick);
}

int knapsack(int W, vector<int> &val, vector<int> &wt) {
    int n = val.size();
    return knapsackRec(W, val, wt, n);
}

int main() {

    vector<int> val = {3, 12, 7, 9, 6};
    vector<int> wt = {2, 4, 3, 5, 2};

    int W = 8;

    cout << knapsack(W, val, wt);

    return 0;
}

The Biggest Problem With Recursion

Recursion works correctly.

But it is slow.

Why?

Because the same problems are solved again and again.

For example:

solve(3, 10)

might get called from multiple paths.

And every time:

• recursion recalculates it fully

This causes huge repetition.

Enter Memoization

Memoization means:

Store already calculated answers.

So next time: instead of recalculating, we directly reuse the answer.

What Gets Stored?

We use:

dp[n][W]

This stores:

Maximum profit possible using first n objects with capacity W.

Meaning of DP State

| State    | Meaning                                            |
| -------- | -------------------------------------------------- |
| dp[5][8] | best profit using first 5 objects and capacity 8   |
| dp[3][5] | best profit using first 3 objects and capacity 5   |
| dp[1][2] | best profit using only first object and capacity 2 |

Very Important Understanding About Memoization:

Many beginners think:

Memoization changes the logic.

No.

The logic stays EXACTLY SAME.

We STILL:

• choose
• not choose

We STILL use recursion.

The ONLY difference is:

We store repeated answers and reuse them.

Memoization Code

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dp;

int knapsackMemo(int W, vector<int> &val,
                 vector<int> &wt, int n) {

    // Base case
    if (n == 0 || W == 0)
        return 0;

    // Already solved
    if (dp[n][W] != -1)
        return dp[n][W];

    int pick = 0;

    // Pick object
    if (wt[n - 1] <= W)
        pick = val[n - 1] +
               knapsackMemo(W - wt[n - 1], val, wt, n - 1);

    // Don't pick object
    int notPick =
        knapsackMemo(W, val, wt, n - 1);

    // Store answer
    return dp[n][W] = max(pick, notPick);
}

int knapsack(int W, vector<int> &val, vector<int> &wt) {

    int n = val.size();

    dp.resize(n + 1, vector<int>(W + 1, -1));

    return knapsackMemo(W, val, wt, n);
}

How to think when you see a 0/1 Knapsack problem?

For every object: Can I take it? Or should I skip it?

If taking is possible:

• try both
• take maximum

And because many states repeat:

• store answers using DP

Therefore, 0/1 Knapsack is a choose/not choose recursion problem with a weight constraint, and memoization simply stores answers of repeated subproblems to avoid recalculation.