0/1 Knapsack Problem

1. Problem Description

The 0/1 Knapsack problem is a classic optimization problem in computer science and dynamic programming. You are given N items, where each item has:

• Weight: how much space or capacity the item takes.
• Value: the benefit or worth of including the item in the knapsack.

The goal is to choose a subset of items such that their total weight does not exceed a given capacity W of the knapsack, and the total value is maximized.

It is called “0/1” because for each item, you can either take it completely (1) or leave it (0) — no partial items allowed.

2. Algorithm

We solve this using dynamic programming (DP) by breaking the problem into subproblems and storing solutions to avoid recomputation.

Definition of DP Table:

We define a 2D table dp[i][w] where:

• i: number of items considered (from the first i items)
• w: current capacity of the knapsack (from 0 to W)
• dp[i][w]: maximum value that can be obtained using the first i items and total capacity w

Transition Relation:

For each item i and each capacity w, we have two choices:

• Don't take the item: dp[i][w] = dp[i-1][w]
• Take the item (if it fits): dp[i][w] = dp[i-1][w - weight[i]] + value[i]

if weight[i] <= w:
    dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
else:
    dp[i][w] = dp[i-1][w]

Time and Space Complexity

• Time Complexity: O(N * W) — where N is the number of items, and W is the knapsack capacity.
• Space Complexity: O(N * W) using a 2D array; can be optimized to O(W) using a 1D array, since only the previous row is needed at each step.

3. Easy Problems

Problem 1: Basic Knapsack

Classic 0/1 Knapsack: Maximize value without exceeding capacity.

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

int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i-1] <= w)
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

Problem 2: Can Fill Exactly?

Determine if it's possible to exactly fill the knapsack to capacity W using any subset of items.

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

bool canFillExact(int W, vector<int>& weights, int n) {
    vector<vector<bool>> dp(n+1, vector<bool>(W+1, false));
    dp[0][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];
            if (w >= weights[i-1])
                dp[i][w] |= dp[i-1][w - weights[i-1]];
        }
    }
    return dp[n][W];
}

4. Intermediate Problems

Problem 3: Count Number of Ways to Fill Knapsack

Count how many different combinations of items can exactly fill the knapsack to a total weight W.

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

int countWays(int W, vector<int>& weights, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];
            if (w >= weights[i-1])
                dp[i][w] += dp[i-1][w - weights[i-1]];
        }
    }
    return dp[n][W];
}

Problem 4: Subset with Given Difference

Given a set of integers, find the number of subsets such that the absolute difference between the sum of two subsets is equal to a given value.

This can be transformed into a knapsack problem by converting the difference condition into a target sum using:

sum(S1) - sum(S2) = diff
=> sum(S1) = (totalSum + diff) / 2

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

int subsetWithDiff(vector<int>& nums, int diff) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if ((sum + diff) % 2 != 0) return 0;
    int target = (sum + diff) / 2;

    vector<int> dp(target+1, 0);
    dp[0] = 1;

    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[target];
}

5. Hard Problem

Problem 5: 0/1 Knapsack with Item Reconstruction

Return not only the maximum achievable value but also the list of item indices that make up this optimal value. This involves backtracking through the dp table to find which items were chosen.

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

pair<int, vector<int>> knapsackWithItems(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i-1] <= w)
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }

    // Backtrack to find selected items
    vector<int> selectedItems;
    int w = W;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            selectedItems.push_back(i-1); // i-1 is the original item index
            w -= weights[i-1];
        }
    }

    return {dp[n][W], selectedItems};
}

6. Conclusion

The 0/1 Knapsack problem demonstrates key principles of dynamic programming: overlapping subproblems and optimal substructure. Mastering it builds a foundation for solving a wide range of optimization problems, such as subset sum, partition problems, and resource allocation tasks.

Understanding both how the algorithm works and why it works is critical to applying it to new variations and constraints.