Problem Overview: The 0/1 Knapsack

Given a maximum capacity (or time limit) W and N distinct items, where each item has a weight (or time cost) and a value, the objective is to maximize the total value of selected items without exceeding the given capacity. Each item can be chosen at most once.

Constraints

• Maximum Capacity W: 1 ≤ W ≤ 1000
• Number of Items N: 1 ≤ N ≤ 100
• Weight and Value per item: 1 to 100

Approach 1: Brute-Force Recursion

The most intuitive method evaluates every possible combination of items. For each item, we make a binary choice: either skip it or include it. This generates a binary tree of decisions with a time complexity of O(2^N), which is highly inefficient and will result in a Time Limit Exceeded error for larger inputs.

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

int maxCapacity, itemCount;
vector<int> itemWeights, itemValues;
int optimalValue = 0;

void exploreChoices(int idx, int capacityLeft, int accumulatedValue) {
    if (capacityLeft < 0) return;
    if (idx == itemCount) {
        optimalValue = max(optimalValue, accumulatedValue);
        return;
    }
    // Decision 1: Skip the current item
    exploreChoices(idx + 1, capacityLeft, accumulatedValue);
    // Decision 2: Include the current item
    exploreChoices(idx + 1, capacityLeft - itemWeights[idx], accumulatedValue + itemValues[idx]);
}

int main() {
    cin >> maxCapacity >> itemCount;
    itemWeights.resize(itemCount);
    itemValues.resize(itemCount);
    for (int i = 0; i < itemCount; ++i) {
        cin >> itemWeights[i] >> itemValues[i];
    }
    exploreChoices(0, maxCapacity, 0);
    cout << optimalValue << endl;
    return 0;
}

Approach 2: Memoized Search (Top-Down DP)

The naive recursive approach suffers from overlapping subproblems. The maximum achievable value for a given item index and remaining capacity is recalculated repeatedly. By storing the results of these subproblems in a cache, we can prune the recursion tree. This top-down approach reduces the time complexity to O(N * W).

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

int maxCapacity, itemCount;
vector<int> itemWeights, itemValues;
vector<vector<int>> memoCache;

int searchWithMemo(int idx, int capacityLeft) {
    if (idx == itemCount) return 0;
    if (memoCache[idx][capacityLeft] != -1) return memoCache[idx][capacityLeft];
    
    // Value if we skip the current item
    int skipValue = searchWithMemo(idx + 1, capacityLeft);
    int pickValue = 0;
    
    // Value if we include the current item
    if (capacityLeft >= itemWeights[idx]) {
        pickValue = itemValues[idx] + searchWithMemo(idx + 1, capacityLeft - itemWeights[idx]);
    }
    
    return memoCache[idx][capacityLeft] = max(skipValue, pickValue);
}

int main() {
    cin >> maxCapacity >> itemCount;
    itemWeights.resize(itemCount);
    itemValues.resize(itemCount);
    memoCache.assign(itemCount + 1, vector<int>(maxCapacity + 1, -1));
    
    for (int i = 0; i < itemCount; ++i) {
        cin >> itemWeights[i] >> itemValues[i];
    }
    cout << searchWithMemo(0, maxCapacity) << endl;
    return 0;
}

Approach 3: Iterative Dynamic Programming (Bottom-Up)

We can eliminate recursion entire by iteratively filling a 2D array. Let dp[i][w] represent the maximum value obtainable considering the first i items with a capacity limit of w. The state transition logic is straightforward: if the current item's weight exceeds the current capacity, we must skip it; otherwise, we take the maximum of skipping or including it.

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

int main() {
    int maxCapacity, itemCount;
    cin >> maxCapacity >> itemCount;
    
    vector<int> itemWeights(itemCount), itemValues(itemCount);
    for (int i = 0; i < itemCount; ++i) {
        cin >> itemWeights[i] >> itemValues[i];
    }
    
    // dp[i][w] stores the max value using first i items with capacity w
    vector<vector<int>> dp(itemCount + 1, vector<int>(maxCapacity + 1, 0));
    
    for (int i = 1; i <= itemCount; ++i) {
        for (int w = 0; w <= maxCapacity; ++w) {
            // Inherit the value from not picking the i-th item
            dp[i][w] = dp[i - 1][w];
            // Check if we can pick the i-th item (Note: 0-indexed arrays)
            if (w >= itemWeights[i - 1]) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - itemWeights[i - 1]] + itemValues[i - 1]);
            }
        }
    }
    
    cout << dp[itemCount][maxCapacity] << endl;
    return 0;
}