0-1 Knapsack Problem

15 Dec 2024

1. Problem Description

In the 0/1 knapsack problem, there are n items and a knapsack with capacity m. Item i has volume volume[i] and value value[i]. Every item has only two choices, take it or leave it, and each item can be taken at most once. The goal is to maximize the total value without exceeding the knapsack capacity.

Directly trying both choices for every item produces 2ⁿ possibilities. Dynamic programming stores repeated subproblems that appear during this decision process, avoiding repeated computation.

2. State and Transition

Let f[j] be the maximum value obtainable after considering the items processed so far, using a knapsack with capacity at most j. When processing an item with volume v and value w, there are two choices:

Do not take it, leaving f[j] unchanged.
Take it, which leaves capacity j - v for earlier items and gives value f[j - v] + w.

Therefore, when j >= v, the transition is:

f[j] = max(f[j], f[j - v] + w);

Capacity j must be processed from large to small. When calculating f[j], f[j - v] is then still the old state that does not use the current item, so the item can be taken at most once. If capacity is processed from small to large, the same item can be used repeatedly in one round, turning the problem into a complete knapsack problem.

3. Example: Maximum Value

The following program reads the knapsack capacity, the number of items, and the volume and value of each item. It outputs the maximum possible value. Its input format matches Luogu P1048: Collecting Herbs: capacity first, followed by the item count.

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

const int N = 10010;
int f[N];

int main() {
    int capacity, n;
    cin >> capacity >> n;

    for (int i = 1; i <= n; i++) {
        int volume, value;
        cin >> volume >> value;

        for (int j = capacity; j >= volume; j--) {
            f[j] = max(f[j], f[j - volume] + value);
        }
    }

    cout << f[capacity];
    return 0;
}

For example, suppose the knapsack capacity is 4 and the three items are (2, 3), (1, 2), and (3, 4), where each pair gives volume and value. Taking the second and third items uses volume 4 and gives total value 6, so the answer is 6.

This one-dimensional implementation runs in O(nm) time and uses O(m) space. The key to 0/1 knapsack is to define what f[j] represents, write the transition for taking or not taking an item, and process capacity in descending order so that every item is used at most once.

0-1 Knapsack Problem

Related Posts