Choose your language!

---

|

0/1 Knapsack Problem – Dynamic Programming

The Knapsack Problem is one of the most fundamental problems in algorithm design and dynamic programming. It appears frequently in interviews and competitive programming.

What is the 0/1 Knapsack Problem?

Imagine we have a backpack with a maximum capacity of W and N items. For each item, two values are known:

• weight w[i]
• value v[i]

Each item can be:

• taken completely
• or not taken at all

Hence this version is called the 0/1 knapsack (0 = we don’t take the item, 1 = we take it).

This problem often appears in optimization, combinatorics, algorithms, and programming competitions. Essentially, we are trying to find the best combination of items so that:

• the total weight does not exceed the backpack capacity W,
• the total value of the selected items is maximized

The item value (v[i]) can represent different things in practice:

• profit or price the item brings,
• utility or importance of the item,
• points, or any measurable quantitative benefit provided by the item,
• in games or simulations – strength, experience, resources, etc.

Although it sounds simple, this problem is very well-known because it is one of the classic examples of dynamic programming.

Problem Description

Given N items, where each item has:

• weight – an integer w[i]
• value – an integer v[i]

A backpack with maximum capacity W is also given. The goal is to select a subset of items so that:

• the total weight of selected items does not exceed W,
• and the sum of their values is maximal.

Each item can be chosen at most once. Items cannot be split or taken multiple times – we either take an item completely or not at all.

Task:
Compute the maximum total value of items that can be placed into a backpack of capacity W.

Example with concrete numbers

Input:

• Number of items: N = 3
• Item weights: w = {1, 3, 4}
• Item values: v = {15, 20, 30}
• Backpack maximum weight: W = 4

Explanation:

• Item 1: weight = 1, value = 15
• Item 2: weight = 3, value = 20
• Item 3: weight = 4, value = 30

The optimal solution is to select items 1 and 2: total weight = 1 + 3 = 4 (≤ W), total value = 15 + 20 = 35, which is the maximum possible.

Output:

• Maximum total value: 35
• Selected items: {1, 2} (or their weights/values: {(1,15),(3,20)})

The solution can be obtained using dynamic programming, either top-down (memoization) or bottom-up (tabulation).

Figure 1: 0/1 knapsack problem in dynamic programming

Naive solution and motivation for dynamic programming

Before moving to an efficient DP solution, it is important to understand what a naive approach looks like. In the simplest version, we try all possible subsets of items (each item is either taken or not taken).

However, the number of combinations is 2^N. For N = 30, that is already over a billion possibilities. Therefore, the brute-force approach is far too slow and cannot be used in competitions.

This is why we introduce dynamic programming: instead of repeatedly recalculating the same subproblems, DP stores their results and uses them to solve the problem in reasonable time.

For competitions: important notes

• Pay attention to limits: always check N and W in the problem statement.
• Variable types – weights and values can often be large. Use long long in C++.
• Edge cases:
  • W = 0
  • N = 0
  • all items heavier than W
  • there is one item that exactly fits into W
• Always check if solution reconstruction is required (which items are taken).

Time complexity, limits, and when DP does not work

The standard DP solution runs in O(N · W) time. This is much better than 2^N, but it has an important property: the runtime depends directly on the value of W.

Therefore, we say that DP for the 0/1 Knapsack is a pseudo-polynomial algorithm – it is not polynomial in the number of input bits, but in the actual value of W.

When does the DP solution fail?

• when W is a very large number (e.g., 10⁷, 10⁸, or more)
• when memory cannot hold the DP table

In such cases, alternative methods are used:

• solving by values instead of weights (another DP approach)
• meet-in-the-middle (for N up to around 40)
• branch & bound or backtracking with heuristics
• approximation and FPTAS algorithms

Definition of DP state

We define:

dp[i][j] = maximum value we can achieve using
           the first i items, if the remaining knapsack capacity is j.

Base cases

• dp[0][j] = 0 → With no items, the value is 0
• dp[i][0] = 0 → If capacity is 0, the value is 0

Transition

If the item is too heavy:

if w[i] > j:
    dp[i][j] = dp[i-1][j]

If it fits, we choose the better option:

dp[i][j] = max(
    dp[i-1][j],                 // do not take the item
    dp[i-1][j - w[i]] + v[i]    // take the item
)

C++ Implementation (with explanations)

In this program, we use dynamic programming to solve the classic 0/1 Knapsack problem. We form a DP table of size (N+1) × (W+1), where:

• i represents the first i items under consideration,
• j represents the knapsack capacity from 0 to W,
• dp[i][j] represents the maximum value achievable using the first i items and capacity j.

Each row of the table corresponds to including more items (1, 2, 3, ..., N). Each column corresponds to a possible knapsack capacity (from 0 to W).

Based on this, we have two choices:

• Do not take item i — the value remains the same as dp[i-1][j]
• Take item i (if its weight ≤ j) — then consider dp[i-1][j−w[i]] + v[i]

The main goal is to find dp[N][W] — the best possible value using all items and the full knapsack capacity.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, W;
    cin >> N >> W;  
    // N = number of items
    // W = maximum knapsack capacity

    vector<int> w(N+1), v(N+1);
    for (int i = 1; i <= N; i++)
        cin >> w[i] >> v[i];  
        // w[i] = weight of the i-th item
        // v[i] = value of the i-th item

    // Create DP table of size (N+1) x (W+1)
    // dp[i][j] = best possible value using first i items and capacity j
    vector<vector<int>> dp(N+1, vector<int>(W+1, 0));

    // Fill the DP table
    for (int i = 1; i <= N; i++) {        // considering the i-th item
        for (int j = 1; j <= W; j++) {    // knapsack capacity from 1 to W

            // Option 1: Do NOT take the i-th item
            dp[i][j] = dp[i-1][j];

            // Option 2: Take the item (if it fits in the remaining capacity)
            if (w[i] ≤ j) {
                dp[i][j] = max(
                    dp[i][j],                   // do not take the item
                    dp[i-1][j - w[i]] + v[i]    // take the item
                );
            }
        }
    }

    // Final answer: best possible value with all items and full capacity
    cout << dp[N][W];
}

Example — DP Table Visualization

How is the table formed in this example?

For N = 4 items and knapsack capacity W = 7, we form a DP table with number of rows = 5 (from 0 to 4) and number of columns = 8 (from 0 to 7).

Row i means: considering the first i items.
Column j means: maximum knapsack capacity is j.

Each cell dp[i][j] tells us: what is the maximum value achievable using items 1..i with capacity j.

Assume we have a knapsack with capacity W = 7 and 4 items:

Item	Weight	Value
1	1	1
2	3	4
3	4	5
4	5	7

DP table with rows corresponding to items:

i\j	0	1	2	3	4	5	6	7
0 (no items)	0	0	0	0	0	0	0	0
1 (item 1: w=1, v=1)	0	1	1	1	1	1	1	1
2 (item 2: w=3, v=4)	0	1	1	4	5	5	5	5
3 (item 3: w=4, v=5)	0	1	1	4	5	6	6	9
4 (item 4: w=5, v=7)	0	1	1	4	5	7	8	9

Important note:
In the last cell dp[4][7], we cannot put the value 11 because that would require taking items 2 and 4: 3 + 5 = 8 > 7 — exceeds the knapsack capacity, so the combination is not allowed.

The optimal solution is to take items 2 and 3 → total value = 4 + 5 = 9.

Conclusion

The Knapsack problem is a classic contest problem because it requires understanding:

• subproblem structure
• DP state formulation
• optimal transitions
• time and memory analysis

Students who master this problem can later easily tackle:

• Unbounded Knapsack
• Subset Sum
• Coin Change
• Partition problem

Additional Materials — More Examples and Visual Explanation

To better understand the dynamic programming technique for the Knapsack problem, below is a visual representation of the DP table, an additional practice problem, and a more advanced implementation that optimizes memory to O(W).

1. Visual DP Table (Example)

Consider the following data:

• Weights: {1, 3, 4}
• Values: {15, 20, 30}
• Maximum knapsack weight: W = 4

DP table (row = number of first considered items, column = knapsack weight):

i \ w	0	1	2	3	4
0 items	0	0	0	0	0
Item 1 (1,15)	0	15	15	15	15
Item 2 (3,20)	0	15	15	20	35
Item 3 (4,30)	0	15	15	20	35

The optimal solution is 35, achieved by combining items with weights 1 and 3.

Reconstructing Selected Items

After filling the DP table and calculating the maximum knapsack value, the next important step is to reconstruct which items were actually selected. To do this, we move backward through the DP matrix dp[i][w].

• Start from the last item: i = n and the maximum weight w = W.
• If dp[i][w] != dp[i-1][w], then item i was taken.
• Then decrease the weight: w -= weight[i].
• Continue with item i-1.

Here is a typical C++ code for reconstruction:

vector<int> reconstructItems(const vector<int>& weights,
                             const vector<int>& values,
                             const vector<vector<int>>& dp,
                             int W)
{
    int n = weights.size();
    int w = W;
    vector<int> chosen;

    for (int i = n; i > 0; i--) {
        // If the value differs, item i-1 is included
        if (dp[i][w] != dp[i-1][w]) {
            chosen.push_back(i);      // store the item index (1-based)
            w -= weights[i-1];        // decrease the remaining weight
        }
    }

    reverse(chosen.begin(), chosen.end());
    return chosen;
}

This way, we obtain the exact set of items that form the optimal knapsack solution. This step is very important because the DP table only gives the maximum value, while this procedure allows us to identify the actual items in the knapsack.

Memory Optimization — 1D DP Table

The standard solution for the knapsack problem uses a DP table of size N × W, which can occupy a large amount of memory. If the maximum capacity of the knapsack is large (e.g. W = 100,000), memory becomes an issue.

The good news is that the 0/1 knapsack can be optimized to use only a single dp[] array of length W+1. This reduces memory usage from O(N·W) to just O(W).

How does it work?

The key idea is that when processing item i, the DP state depends only on the previous row (i-1). Instead of storing all rows, we use a single array and update it backwards:

// dp[j] = maximum value for capacity j
vector<int> dp(W+1, 0);

for (int i = 1; i <= N; i++) {
    // important: iterate BACKWARDS to avoid overwriting needed values
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

Why must we iterate backwards?

If we iterated forwards (from 0 → W), the newly updated dp[j] value would be used immediately for the next transition within the same iteration, which would incorrectly simulate the unbounded knapsack (item used multiple times).

Therefore, for the 0/1 knapsack: always iterate j from W down to w[i].

When is the 1D optimization NOT applicable?

• when you need to reconstruct the chosen subset → you must store the full 2D table (or use a separate parent array)
• when W is not too large and the 2D DP fits into memory anyway
• when solving a knapsack variant where transitions require access to DP in a different direction

Bonus Chapter — Knapsack Problem Variants

There are many versions of the knapsack problem, each with a different DP approach. These are the most important ones:

1) Unbounded Knapsack (each item can be used unlimited times)

Similar to the basic version, but transitions are calculated so that an item may be chosen more than once. The code differs in one key detail: dp is updated forwards (j from w[i] to W).

// j moves forward → the item can be used multiple times
for (int j = w[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

2) Multiple (Bounded) Knapsack — each item has a limited quantity

Each item can be used k times (e.g. you have 5 identical bottles). The solution typically uses:

• binary splitting technique (converting counts into 1,2,4,... bundles)
• or 3D DP if the counts are small

This variant lies between the 0/1 and unbounded versions.

3) Multidimensional Knapsack

Similar to the standard knapsack, but instead of one constraint (weight) there are two or more restrictions (e.g. weight and volume).

The DP is no longer 2D, but for example 3D:

// example: DP[i][w][vol]
dp[i][w][vol] = maximum value

This variant is much more demanding and is used in real-world systems (e.g. packaging, logistics, space optimization).

This chapter provides a broader view of the knapsack problem and its applications. For serious competitive programming, understanding all variants is essential.

For Competitive Programming — Key Things to Watch Out For

In competitive knapsack (Knapsack) problems, mistakes most often do not come from the DP formula itself, but from incorrect assumptions about limits and data types. Here is a short list of things you should always check before submitting a solution.

1) Limits of N and W

• N — number of items (can be 1000, 5000 or more)
• W — maximum knapsack capacity

Before choosing the method, check the scale of the values:

• If W ≤ 2000 → standard 2D DP works without issues.
• If W ≤ 200,000 → might work with 1D optimization (if reconstruction is not required).
• If W ≥ 10⁷ → DP becomes practically unusable (memory = problem).

2) Data Types

• Values can be large → use long long.
• The total value may exceed a 32-bit int if N is large.
• The DP table may require enormous memory → check if it fits:

dp[N+1][W+1]   →   number of elements = (N+1)*(W+1)
  • each int = 4 bytes
  • 1e8 elements → 400 MB → too much!

3) Edge Cases

• N = 0 or W = 0
• items with weight 0 (sometimes intentionally included!)
• value = 0 (affects DP structure)
• all items heavier than W → result = 0

In many competitive problems, these inputs are exactly what cause WA (Wrong Answer) even when the main code is correct.

Algorithm Complexity and Constraints

Pseudo-Polynomial Complexity

The time complexity of the classic knapsack is:

O(N · W)

This is called pseudo-polynomial because it does not depend on the number of digits of W, but on its numeric value. If W grows by a factor of 10, the time also grows ×10.

When does DP perform poorly?

• when W is extremely large (e.g. 10⁷ to 10⁹)
• when the sum of weights is huge
• when memory is limited (e.g. 256MB limit in online contests)

In these situations the DP approach becomes infeasible because:

• the dp array cannot fit into memory
• execution time becomes too slow

What to use instead of DP?

If W is extremely large, competitors often switch to:

• meet-in-the-middle (for N ≤ 40)
• branch & bound techniques
• heuristics / greedy (if the problem allows it)
• bitset DP (for Subset Sum variants)
• DP over total value (when values are small, weights large)

DP Over Value (important trick!)

If the values are small (up to e.g. 10³), and the weights are huge:

// dp[v] = minimum weight needed to achieve value v

This transforms the complexity from O(NW) to O(N · sum_of_values).

These observations are extremely useful for preparing for competitions such as OI, IOI, CEOI, and others. Understanding the constraints allows you to quickly identify which version of the algorithm to apply.

Hidden Mini Quiz — 0/1 Knapsack Problem

Click to test your knowledge of knapsack basics and DP solutions!

Open Quiz

Mini Quiz: Do You Understand the 0/1 Knapsack Problem?

1. What is the correct DP relation for the 0/1 Knapsack problem?

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
dp[i][w] = dp[i-1][w] + dp[i-1][w - weight[i]]
dp[i][w] = dp[i][w-1] + value[i]
Show Answer

2. If W = 0 or N = 0, what will dp[N][W] be?

0
1
Undefined
Show Answer

3. What is the main idea behind reconstructing the chosen items?

Start from dp[N][W] and check if an item was taken based on changes in value
Simply sum all values
Use brute-force to find all items
Show Answer

4. When is the standard DP solution pseudo-polynomial?

When the time depends only on the number of items N
When the time depends directly on W, not the number of bits in the input
When using a top-down approach
Show Answer

5. What is good practice when both W and N are large?

Use a full 2D DP table
Consider alternative methods (meet-in-the-middle, value-based DP, approximations)
Increase stack memory and run standard DP anyway
Show Answer

□ Reset Quiz

Practice Tasks (with instructions, without solutions)

Task 1:

A group of items is given, each with a weight and a value. Each item can be taken at most once. Determine the maximum total value that can be packed into a knapsack of capacity W = 25.

• Weights: {4, 7, 9, 12, 13}
• Values: {10, 13, 18, 22, 23}

Instruction (short):
Create a DP table of size (n+1) × (W+1) and fill it using the standard transition:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
  

Pay special attention to the case when weight[i] > w — then the value is simply copied from the previous row.

Show / Hide Instructions

Instructions — how to think while filling the DP table

Meaning of a cell:
dp[i][j] represents the maximum value obtainable by using the first i items and a knapsack capacity of j.

Rows correspond to items (from 0 to n), and columns to the available capacity (from 0 to W).

How is dp[i][j] computed?

1. If item i does not fit (weight[i] > j) → dp[i][j] = dp[i-1][j].
2. Otherwise, choose the maximum between:
   • not taking item i
   • taking item i and adding its value

Once the table is filled, the answer is found in cell dp[n][W].

□ Tip:
Before checking the solution, try on your own:

• to estimate which item combinations might fit into the knapsack
• to roughly predict the maximum possible value

Even a partial attempt significantly helps understanding.

Show Solution

⚠ Warning:
The solution is intended for verification and learning. If you have not tried solving it yourself, it is recommended to go back and attempt to fill in at least part of the DP table first.

Solution — DP Table, Reconstruction and Full C++ Code

1) Filled table (dp[i][j]) for the given example

Parameters: n = 5, W = 25
Weights (index 1..5): 4, 7, 9, 12, 13
Values (index 1..5): 10, 13, 18, 22, 23

The table is shown row-by-row (i = 0..5). Each row contains values dp[i][0..25]. Row i means: using the first i items.

How to read the table: cell dp[3][9] = 18 means that with the first 3 items and capacity 9 we can obtain a maximum value of 18. Finally, dp[5][25] = 50 is the answer.

2) Solution reconstruction

• item 1 (4, 10)
• item 3 (9, 18)
• item 4 (12, 22)

Total weight = 25
Total value = 50

3) C++ solution with comments

Copy

2. Knapsack optimized to O(W) memory

Problem statement

The classic 0/1 Knapsack problem is given. For a knapsack capacity W and a list of items (each with weight w[i] and value v[i]), compute the maximum total value that can fit in the knapsack.

Your task is to write an optimized solution that uses only O(W) memory (a one-dimensional DP array).

Most important rule: iterate the weights backwards.

Show / Hide instructions

Instructions

For each item i, the DP array is updated in reverse:

for (int weight = W; weight >= w[i]; weight--) {
    dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
}

This prevents using the same item more than once and correctly simulates the 2D DP table.

□ Learning tip:
Before checking the solution, try to answer:

• Why must the weight loop go backwards?
• What would happen if we looped forwards?

Even a short attempt greatly improves understanding.

Show solution

⚠ Warning:
The solution is provided to check and understand the idea. If you haven't tried it yourself — it is recommended to go back and attempt at least a basic implementation first.

Solution — detailed explanation

// Knapsack optimized to O(W) memory
#include 
#include 
using namespace std;

int main() {
    vector w = {1, 3, 4};
    vector v = {15, 20, 30};

    int W = 7;
    vector dp(W + 1, 0);

    for (int i = 0; i < w.size(); i++) {
        for (int weight = W; weight >= w[i]; weight--) {
            dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
        }
    }

    cout << "Maximum value: " << dp[W] << endl;
    return 0;
}

Visualization of the 1D DP array

Let's observe how the DP array changes for each item. The index represents knapsack capacity; the value is the maximum gain.

Initial state:
dp = [0, 0, 0, 0, 0, 0, 0, 0]

Item 1: weight = 1, value = 15
dp = [0, 15, 15, 15, 15, 15, 15, 15]

Item 2: weight = 3, value = 20
dp = [0, 15, 15, 20, 35, 35, 35, 35]

Item 3: weight = 4, value = 30
dp = [0, 15, 15, 20, 35, 45, 45, 50]

Since we iterate backwards, values like dp[weight - w[i]] still represent the state before considering the current item, ensuring that each item is used at most once (0/1 Knapsack).

3. Reconstructing the Selected Items (0/1 Knapsack)

Problem statement

After filling the dynamic programming table for the classical 0/1 Knapsack problem and computing the maximum achievable value, it is often necessary to know which exact items form that optimal solution.

You are given an already filled DP table dp[i][w], where dp[i][w] represents the maximum value obtainable using the first i items and knapsack capacity w.

Your task is to implement an algorithm for reconstructing the chosen items — i.e. determining which items are included in the optimal solution.

Reconstruction is performed backwards, starting from the state i = n and w = W, by analyzing changes in the DP table.

You should write C++ code that returns the indices of the selected items (1-based) that form the optimal knapsack content.

Example inputs and expected outputs

Example 1

Input:
weights = {1, 3, 4}
values  = {15, 20, 30}
W = 7

Filled DP table (dp):
i\w | 0  1  2  3  4  5  6  7
--------------------------------
0   | 0  0  0  0  0  0  0  0
1   | 0 15 15 15 15 15 15 15
2   | 0 15 15 20 35 35 35 35
3   | 0 15 15 20 35 45 45 50

Expected output:
Selected items: 1 3
  

Explanation:
Item 1 (weight 1, value 15) and item 3 (weight 4, value 30) together give the maximum value of 45 with capacity 7.

Example 2

Input:
weights = {2, 5, 3, 4}
values  = {6, 10, 7, 12}
W = 7

Expected output:
Selected items: 1 4
  

Example 3

Input:
weights = {4, 2, 3}
values  = {8, 5, 6}
W = 5

Expected output:
Selected items: 2 3
  

Show / hide hint

Hint — how reconstruction works

Reconstruction relies on the fact that in the DP table, any change in value compared to the previous row occurs only if the current item is included in the solution.

1. Start from i = n and w = W.
2. If dp[i][w] == dp[i-1][w] → the item was not selected.
3. If dp[i][w] != dp[i-1][w] → item i was selected.
4. If the item was selected, reduce the capacity: w -= weights[i-1].
5. Continue while i > 0 and w >= 0.

Key condition in the code:

if (dp[i][w] != dp[i-1][w]) {
    chosen.push_back(i);
    w -= weights[i-1];
}
    

Since items are discovered in reverse order, the resulting list must be reversed to obtain increasing indices.

□ Learning tip:
Before looking at the solution, think about:

• Why does comparing with dp[i-1][w] work?
• What does it mean if the values are equal?
• Why is the capacity reduced only when the item is selected?

Understanding these questions is essential for all DP problems that involve reconstruction.

Show solution

⚠ Warning:
The solution is provided for verification and understanding. If you have not tried solving it yourself, it is recommended to do so before reading the code.

Solution — complete C++ code with comments

// Reconstructing selected items from DP table (0/1 Knapsack)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Returns 1-based indices of selected items
vector<int> reconstructItems(const vector<int>& weights,
                             const vector<vector<int>>& dp,
                             int W)
{
    int n = weights.size();
    int w = W;
    vector<int> chosen;

    // Traverse the DP table backwards
    for (int i = n; i > 0; --i) {
        // If value differs, item i was selected
        if (dp[i][w] != dp[i-1][w]) {
            chosen.push_back(i);        // 1-based index
            w -= weights[i-1];          // reduce remaining capacity
        }
    }

    // Reverse order since we traversed backwards
    reverse(chosen.begin(), chosen.end());
    return chosen;
}

int main() {
    vector<int> weights = {1, 3, 4};
    int W = 7;

    vector<vector<int>> dp = {
        {0,0,0,0,0,0,0,0},
        {0,15,15,15,15,15,15,15},
        {0,15,15,20,35,35,35,35},
        {0,15,15,20,35,45,45,50}
    };

    vector<int> result = reconstructItems(weights, dp, W);

    cout << "Selected items: ";
    for (int idx : result) {
        cout << idx << " ";
    }
    cout << endl;

    return 0;
}
    

Conclusion

Reconstruction is a natural continuation of a DP solution. Once you understand this principle, the same pattern applies to: LCS, Edit Distance, Subset Sum, and many other dynamic programming problems.

4. Unbounded Knapsack

Problem statement

In this variant of the knapsack problem, known as the Unbounded Knapsack, each item can be used an unlimited number of times.

This means that, unlike the classical 0/1 Knapsack problem, there is no restriction that an item can be chosen only once.

The key implementation difference lies in the way the dynamic programming array is filled:

• 0/1 Knapsack — capacity is iterated backwards
• Unbounded Knapsack — capacity is iterated forwards

Your task is to write a program that solves the Unbounded Knapsack problem using a 1D DP array.

Task requirements

• read the number of items N and knapsack capacity W
• read arrays of weights w[i] and values v[i]
• use a DP array of length W + 1
• allow unlimited usage of each item
• output the maximum possible value for capacity W

Most important implementation rule:
capacity j must be iterated forwards.

// each item can be used multiple times
for (int j = w[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
  

Show / hide hint

Hint — how Unbounded Knapsack works

The essence of the Unbounded Knapsack problem is that the DP state dp[j] may reuse the same item multiple times.

The DP array has the following meaning:

dp[j] = maximum value that can be achieved
        with knapsack capacity j
    

Difference compared to 0/1 Knapsack:

• 0/1 Knapsack
  → each item can be used at most once
  → j goes backwards
• Unbounded Knapsack
  → items can be used unlimited times
  → j goes forwards

When j is iterated forwards, the value dp[j - w[i]] may already include the same item — which automatically enables multiple usage.

DP initialization:

dp[0] = 0
dp[j] = 0 for all j > 0
    

The final answer is always stored in dp[W].

□ Learning tip:
Before looking at the solution, try to answer:

• Why are we allowed to iterate forwards in this problem?
• What would happen if we iterated backwards?
• How does DP implicitly allow item repetition?

If you understand these questions, you understand the entire Unbounded Knapsack problem.

Show solution

⚠ Warning:
The solution is provided for verification and understanding. It is recommended to try writing at least a basic version on your own before reading the code.

Solution — complete C++ code with comments

// Unbounded Knapsack -- 1D DP solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> w(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    // dp[j] = maximum value for capacity j
    vector<int> dp(W + 1, 0);

    // Iterate through all items
    for (int i = 0; i < N; i++) {

        // In Unbounded Knapsack, j goes FORWARDS
        for (int j = w[i]; j <= W; j++) {

            // Option 1: do not take the item
            // Option 2: take the item (and we may take it again)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // Maximum value for capacity W
    cout << dp[W] << endl;
    return 0;
}
    

Example inputs and outputs

Input:
3 7
2 4
3 5
4 7

Output:
13
    

Input:
2 10
6 30
3 14

Output:
42
    

Input:
1 10
2 5

Output:
25
    

Conclusion

Unbounded Knapsack is a natural extension of the 0/1 Knapsack problem. Understanding the difference in capacity iteration direction opens the door to many other DP problems (e.g. coin change, rod cutting).

5. Multiple (Bounded) Knapsack

Problem statement

In this problem we consider a variant of the knapsack problem where each item is available in a limited number of copies. This variant is known as the Multiple or Bounded Knapsack.

For each item we are given:

• w[i] — weight of the i-th item
• v[i] — value of the i-th item
• c[i] — maximum allowed number of copies

The knapsack has a maximum capacity W. The goal is to select items (without exceeding the allowed quantities) such that the total value is maximized.

This problem lies between 0/1 Knapsack and Unbounded Knapsack:

• an item cannot be taken only once (as in 0/1 Knapsack)
• but it also cannot be taken an unlimited number of times

Your task is to implement the Multiple (Bounded) Knapsack using one of the following techniques:

• binary splitting (recommended and efficient)
• or 3D DP (dp[i][w][k] — conceptually simpler, but time- and memory-inefficient)

Show / hide hint

Hint — solution idea (Binary Splitting)

Since each item can be used at most c[i] times, we cannot directly apply the standard 0/1 or Unbounded Knapsack algorithms.

An efficient solution is to use the binary splitting technique (binary decomposition of quantities).

The idea is to decompose c[i] into a sum of powers of two:

c = 13 → 1 + 2 + 4 + 6
    

Each of these parts is treated as a separate 0/1 item:

• weight = k · w[i]
• value = k · v[i]

In this way, the bounded problem is transformed into a classical 0/1 Knapsack problem with approximately O(log c[i]) new items per original item.

Why does this work?

• any quantity from 0 to c[i] can be represented as a combination of binary packages
• the number of items in DP is drastically reduced
• we can use standard 1D DP with backward iteration over weight

Illustrative example

N = 3, W = 10
w = [3, 2, 5]
v = [5, 3, 10]
c = [3, 4, 1]

After binary splitting, we obtain the following 0/1 items:

(3,5), (6,10), (2,3), (4,6), (2,3), (5,10)
(weight, value)

The standard 0/1 Knapsack algorithm is then applied to this set of items.

□ Learning tip:
Before looking at the solution, try to answer:

• Why is 3D DP impractical for large inputs?
• How does binary splitting preserve quantity limits?
• Why do we iterate weight backwards after splitting?

If you understand these questions, you understand the entire Multiple Knapsack problem.

Show solution

⚠ Warning:
The solution is provided for verification and understanding. It is recommended to try implementing binary splitting on your own before reading the code.

Solution — Binary Splitting + 0/1 Knapsack

// Multiple (Bounded) Knapsack using Binary Splitting

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

int main() {
    int N = 3;
    int W = 10;

    vector<int> w = {3, 2, 5};
    vector<int> v = {5, 3, 10};
    vector<int> c = {3, 4, 1};

    // New 0/1 items after decomposition
    vector<pair<int,int>> items;

    // Binary splitting
    for (int i = 0; i < N; i++) {
        int k = c[i];
        int p = 1;

        while (p <= k) {
            items.push_back({p * w[i], p * v[i]});
            k -= p;
            p *= 2;
        }

        if (k > 0) {
            items.push_back({k * w[i], k * v[i]});
        }
    }

    // Standard 0/1 Knapsack DP
    vector<int> dp(W + 1, 0);

    for (auto &item : items) {
        for (int j = W; j >= item.first; j--) {
            dp[j] = max(dp[j], dp[j - item.first] + item.second);
        }
    }

    cout << "Maximum value = " << dp[W] << endl;
    return 0;
}
    

Final result for the given example

For capacity W = 10, the maximum value is:

dp[10] = 18
    

One optimal combination of items:

• 1 × (3, 5)
• 1 × (2, 3)
• 1 × (5, 10)

Binary splitting + 1D DP produces the same result as 3D DP, but with significantly lower memory usage and better time efficiency.

Conclusion

Multiple Knapsack serves as a bridge between the 0/1 and Unbounded variants. Binary splitting is a standard technique frequently used in competitive programming and algorithm courses.

6. Multidimensional Knapsack (Multiple Constraints)

Problem statement

In this variant of the knapsack problem, each item has multiple constraints. The most common ones are weight and volume, but in general the problem may involve more resources (e.g. time, energy, budget).

For each item we are given:

• w[i] — weight of the i-th item
• vol[i] — volume of the i-th item
• v[i] — value of the i-th item

The knapsack has two independent constraints:

• maximum allowed weight W
• maximum allowed volume V

We need to select a subset of items such that:

• total weight ≤ W
• total volume ≤ V
• total value is maximized

Each item can be taken at most once (0/1 variant).

Show / hide hint

Hint — Multidimensional Knapsack

This is a natural extension of the classical 0/1 Knapsack problem. Instead of a single constraint (weight), we now have two independent resources.

The most straightforward and intuitive approach is to use three-dimensional dynamic programming.

dp[i][w][vol] = maximum value achievable
                using the first i items,
                with total weight ≤ w
                and total volume ≤ vol

DP transitions

For each item i, there are two choices:

• Do not take the item:
  dp[i][w][vol] = dp[i-1][w][vol]
• Take the item (only if it fits both constraints):

  dp[i][w][vol] =
  max(dp[i-1][w][vol],
      dp[i-1][w - w[i]][vol - vol[i]] + v[i])
  

Important: the item must satisfy both constraints simultaneously. If it violates even one of them, it cannot be chosen.

Example

N = 3
W = 5
V = 6

w   = [1, 2, 3]
vol = [3, 2, 4]
v   = [10, 20, 30]

Example intuition

• Item 1: (w=1, vol=3, v=10)
• Item 2: (w=2, vol=2, v=20)
• Item 3: (w=3, vol=4, v=30)

Combination of items 1 and 3:

• Weight: 1 + 3 = 4 ≤ 5
• Volume: 3 + 4 = 7 ❌ (does not fit)

This combination is not allowed. The following optimal options remain:

• Item 1 + Item 2
  Weight = 3, volume = 5, value = 30
• Only Item 3
  Weight = 3, volume = 4, value = 30

The maximum value for this example is:

Maximum value = 30

□ Learning tip:
Before looking at the solution, think about:

• How would the problem scale with three or more resources?
• Why can’t we optimize weight and volume independently?
• How does this problem differ from the standard 0/1 Knapsack?

If you understand these questions, you understand the essence of multidimensional DP.

Show solution

⚠ Warning:
The solution is provided to explain the algorithm. It is recommended to try implementing the basic DP yourself before looking at the code.

Solution — 3D Dynamic Programming

// Multidimensional Knapsack (Weight + Volume) — 0/1 variant

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

int main() {
    int N = 3;
    int W = 5;
    int V = 6;

    vector<int> w   = {1, 2, 3};
    vector<int> vol = {3, 2, 4};
    vector<int> v   = {10, 20, 30};

    // dp[i][ww][vv] = maximum value
    vector<vector<vector<int>>> dp(
        N + 1,
        vector<vector<int>>(W + 1, vector<int>(V + 1, 0))
    );

    for (int i = 1; i <= N; i++) {
        for (int ww = 0; ww <= W; ww++) {
            for (int vv = 0; vv <= V; vv++) {

                // Do not take the item
                dp[i][ww][vv] = dp[i-1][ww][vv];

                // Take the item if it fits
                if (ww >= w[i-1] && vv >= vol[i-1]) {
                    dp[i][ww][vv] = max(
                        dp[i][ww][vv],
                        dp[i-1][ww - w[i-1]][vv - vol[i-1]] + v[i-1]
                    );
                }
            }
        }
    }

    cout << "Maximum value = "
         << dp[N][W][V] << endl;

    return 0;
}

Complexity note

• Time complexity: O(N · W · V)
• Memory complexity: O(N · W · V)

In practice, a 2D optimization (dp[w][vol]) is often used, iterating backwards over both resources, reducing memory usage to O(W · V).

Conclusion

Multidimensional Knapsack demonstrates the power of dynamic programming in problems with multiple constraints. Understanding this pattern makes it easier to solve real-world optimization problems involving several limited resources at the same time.

4. Povezane stranice

• Uvod u DP — osnovna ideja
• DP: Fibonacci sa memoizacijom
• DP: Subset Sum
• Matematički algoritmi — Fibonacci

---

Previous
​|< DP: Fibonacci with memoization

Next
DP: Longest Common Subsequence (LCS) >|

---