Grade 11 · Dynamic programmingCitește în română

The knapsack problem (0/1 version)

Original: Problema rucsacului (varianta discretă)

O(n²)C++1769 lines1 example

The idea

A knapsack holds at most G kilograms; there are n objects with weights g[i] and values v[i], and an object is taken whole or not at all. Here greedy by value per kilogram no longer works. best[i][c] is the maximum value using only the first i objects and a capacity c: either we do not take object i (best[i-1][c]), or we take it, if it fits (best[i-1][c - g[i]] + v[i]). To find the chosen objects we go backwards: if best[i][c] differs from best[i-1][c], object i was taken. The maximum value and the indices of the chosen objects are printed.

Original description (Romanian)

Un rucsac suportă cel mult G kilograme; avem n obiecte cu greutățile g[i] și valorile v[i], iar un obiect se ia întreg sau deloc. Aici greedy-ul după valoare pe kilogram nu mai merge. best[i][c] este valoarea maximă folosind doar primele i obiecte și o capacitate c: fie nu luăm obiectul i (best[i-1][c]), fie îl luăm, dacă încape (best[i-1][c - g[i]] + v[i]). Pentru a afla obiectele alese mergem înapoi: dacă best[i][c] diferă de best[i-1][c], obiectul i a fost luat. Se afișează valoarea maximă și numerele obiectelor alese.

Complexity
O(n · G) time and memory
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

4 10
5 10
4 40
6 30
3 50

Expected output

90
2 4

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

rucsacul-discret.cpp
/*
 * Titlu: Problema rucsacului (varianta discretă)
 * Clasa: 11
 * Capitol: Programare dinamică
 * Descriere: Un rucsac suportă cel mult G kilograme; avem n obiecte cu greutățile g[i] și
 *            valorile v[i], iar un obiect se ia întreg sau deloc. Aici greedy-ul după
 *            valoare pe kilogram nu mai merge. best[i][c] este valoarea maximă folosind
 *            doar primele i obiecte și o capacitate c: fie nu luăm obiectul i
 *            (best[i-1][c]), fie îl luăm, dacă încape (best[i-1][c - g[i]] + v[i]).
 *            Pentru a afla obiectele alese mergem înapoi: dacă best[i][c] diferă de
 *            best[i-1][c], obiectul i a fost luat. Se afișează valoarea maximă și
 *            numerele obiectelor alese.
 * Complexitate: O(n · G) timp și memorie
 *
 * Exemplu
 * Intrare:
 * 4 10
 * 5 10
 * 4 40
 * 6 30
 * 3 50
 * Ieșire:
 * 90
 * 2 4
 */
#include <iostream>
using namespace std;

int g[105], v[105], best[105][10005];

int main()
{
    int n, G;
    cin >> n >> G;
    for (int i = 1; i <= n; i++)
    {
        cin >> g[i] >> v[i];
    }

    for (int i = 1; i <= n; i++)
    {
        for (int c = 0; c <= G; c++)
        {
            best[i][c] = best[i - 1][c];
            if (g[i] <= c && best[i - 1][c - g[i]] + v[i] > best[i][c])
            {
                best[i][c] = best[i - 1][c - g[i]] + v[i];
            }
        }
    }
    cout << best[n][G] << '\n';

    int ales[105], cate = 0, c = G;
    for (int i = n; i >= 1; i--)
    {
        if (best[i][c] != best[i - 1][c])
        {
            ales[cate++] = i;
            c -= g[i];
        }
    }
    for (int i = cate - 1; i >= 0; i--)
    {
        cout << ales[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.