0/1 Knapsack Problem

0/1 Knapsack Problem

Medium DSA Dynamic Programming 39 views
Explanation Complexity

Problem Statement

Given weights and values determine the maximum value that can be obtained in a knapsack of fixed capacity using DP.
You are given:
  • An array weights[]
  • An array values[]
  • A knapsack with fixed capacity W
Each item can be:
 • Taken once (1)
 • Or not taken (0)
Your task is to find the maximum total value you can put in the knapsack without exceeding capacity.

Input Format

• Integer array weights[]
• Integer array values[]
• Integer W (capacity)

Output Format

One integer → maximum value

Example

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
W = 7

9

Concept Explanation

You have a bag that can hold 7 weight units.
You must choose items so that:
 • Total weight ≤ 7
 • Total value is maximum
Best choice:
Take items with weight 3 (value 4) and weight 4 (value 5)
Total weight = 7
Total value = 9 ✔
Brute Force Problem
 If we try all combinations:
  • Each item has 2 choices (take / not take)
  • Total combinations = 2ⁿ ❌ (very slow)
DP Idea:
Dynamic Programming means:
“Solve small problems first and use them to solve bigger problems.”
DP Table Meaning (Easy)
Let:
dp[i][w]
Means:
Maximum value using first i items with knapsack capacity w

Step-by-Step Explanation

Step-by-Step Solution (Recommended)
🔹 Step 1: Create DP Table
   dp[n+1][W+1]
🔹 Step 2: Base Case
If no items or capacity is 0 → value = 0
🔹 Step 3: Fill the Table
For each item:
If item weight ≤ current capacity:
Take max of:
Not taking the item
Taking the item
Else:
Skip the item
🔹 Step 4: Final Answer
dp[n][W]

DP Formula 
if (weights[i-1]

Complexity Analysis

O(n × W)
O(n × W)

Concept Explanation

You have a bag that can hold 7 weight units.
You must choose items so that:
 • Total weight ≤ 7
 • Total value is maximum
Best choice:
Take items with weight 3 (value 4) and weight 4 (value 5)
Total weight = 7
Total value = 9 ✔
Brute Force Problem
 If we try all combinations:
  • Each item has 2 choices (take / not take)
  • Total combinations = 2ⁿ ❌ (very slow)
DP Idea:
Dynamic Programming means:
“Solve small problems first and use them to solve bigger problems.”
DP Table Meaning (Easy)
Let:
dp[i][w]
Means:
Maximum value using first i items with knapsack capacity w

Step-by-Step Explanation

Step-by-Step Solution (Recommended)
🔹 Step 1: Create DP Table
   dp[n+1][W+1]
🔹 Step 2: Base Case
If no items or capacity is 0 → value = 0
🔹 Step 3: Fill the Table
For each item:
If item weight ≤ current capacity:
Take max of:
Not taking the item
Taking the item
Else:
Skip the item
🔹 Step 4: Final Answer
dp[n][W]

DP Formula 
if (weights[i-1]

Input / Output Format

Input Format
• Integer array weights[]
• Integer array values[]
• Integer W (capacity)
Output Format
One integer → maximum value

Examples

Input:
weights = [1, 3, 4, 5] values = [1, 4, 5, 7] W = 7
Output:
9

Example Solution (Public)

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

int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(
                    dp[i - 1][w],
                    val[i - 1] + dp[i - 1][w - wt[i - 1]]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

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

    cout << knapsack(W, wt, val);
    return 0;
}

Official Solution Code

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

int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(
                    dp[i - 1][w],
                    val[i - 1] + dp[i - 1][w - wt[i - 1]]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

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

    cout << knapsack(W, wt, val);
    return 0;
}
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.