01 Knapsack Problem

Problem Statement

Given item_count items and a knapsack with capacity capacity, each item has a weight w and value val. Calculate the maximum total value achievable without exceeding the knapsack capacity.

Input Example:

5 20
1 6
2 5
3 8
5 15
3 3 

Output Example:

37

Solution Idea

The 01 knapsack problem restricts each item to be either included once or excluded. We use dynamic programming to solve this by breaking it into subproblems.

Define a 2D DP array dp, where dp[i][j] represents the maximum value obtainable using the first i items with a knapsack capacity of j.

Initialization:

• If there are no items (i = 0) or the capacity is 0 (j = 0), the maximum value is 0.

Recurrence Relation:

• If the weight of the i-th item exceeds the current capacity j, we cannot include it. Thus, dp[i][j] = dp[i-1][j].
• If the item can be included, decide whether including it yields a higher value. The recurrence becomes dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + val[i]).

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int item_count, capacity;
    cin >> item_count >> capacity;

    vector<int> weights(item_count + 1, 0);
    vector<int> values(item_count + 1, 0);
    for (int i = 1; i <= item_count; ++i) {
        cin >> weights[i] >> values[i];
    }

    vector<vector<int>> dp(item_count + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= item_count; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            if (j < weights[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }

    cout << dp[item_count][capacity] << endl;

    return 0;
}

Complete Knapsack Problem

Problem Statement

Given item_count items and a knapsack with capacity capacity, each item has a weight w and value val. Each item can be taken infinitely many times. Calculate the maximum total value achievable without exceeding the knapsack capacity.

Input Example:

5 20
1 6
2 5
3 8
5 15
3 3 

Output Example:

120

Solution Idea

The complete knapsack allows each item to be taken multiple times. The DP array definition remains similar to 01 knapsack, but the recurrence relation is adjusted to account for multiple selections.

Recurrence Relation:

• If the weight of the i-th item exceeds j, carry over from dp[i-1][j].
• If the item can be included, the recurrence becomes dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + val[i]), where dp[i][j - w[i]] allows taking the same item again.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int item_count, capacity;
    cin >> item_count >> capacity;

    vector<int> weights(item_count + 1, 0);
    vector<int> values(item_count + 1, 0);
    for (int i = 1; i <= item_count; ++i) {
        cin >> weights[i] >> values[i];
    }

    vector<vector<int>> dp(item_count + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= item_count; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            if (j < weights[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weights[i]] + values[i]);
            }
        }
    }

    cout << dp[item_count][capacity] << endl;

    return 0;
}