0/1 Knapsack Problem Fix ved hjælp af dynamisk programmeringseksempel

Hvad er rygsækproblemet?

Rullesæk problem is a classic combinatorial optimization problem. A supermarket stores n packages (n ≤ 100). Package i has weight W[i] ≤ 100 and value V[i] ≤ 100. A thief cannot carry weight exceeding capacity M (M ≤ 100). Which packages should the thief take to maximize total value?

Input:

• Maksimal vægt M og antallet af pakker n.
• Array af vægt W[i] og tilsvarende værdi V[i].

Output:

• Maximum total value obtainable within the capacity.
• The exact set of packages the thief should take.

The Knapsack algorithm splits into two well-known variants:

• 0/1 Knapsack Problem solved by Dynamic Programming. Each package is either taken whole or left behind — no fractional pieces and no duplicates.
• Fractional Napsack Problem solved by a Greedy Strategy. Here you may take a fraction of any package to fill the remaining capacity.

Sådan løses knapsækproblem ved hjælp af dynamisk programmering med eksempel

Divide-and-conquer splits a big problem into subproblems, then keeps splitting until each subproblem is easy. Plain recursion, however, often solves the same subproblem many times and wastes work.

The core idea of Knapsack Dynamic Programming is to store every solved subproblem in a table. Repeat calls read the answer instead of recomputing it, turning an exponential recursion into polynomial-time code.

Løs Knapsack-problem ved hjælp af dynamisk programmering

To design a Dynamic Programming solution, you follow four steps:

• Solve the smallest subproblems first.
• Derive a recurrence that builds a subproblem answer from smaller ones.
• Store subproblem answers in a table computed bottom-up using the recurrence.
• Assemble the final answer from the fully populated table.

Analyser 0/1 Rullesæk-problemet

The optimal value depends on two independent factors:

1. How many packages are still being considered.
2. The remaining weight the knapsack can still store.

Because the objective function depends on two quantities, the table of options must be two-dimensional. Let B[i][j] denote the maximum value when choosing among packages {1, …, i} with weight limit j.

• The final answer is B[n][M], the best total value across all n packages under capacity M.
• The total selected weight is always bounded by the current capacity: B[i][j] ≤ j.

Example: if B[4][10] = 8, the best total weight from the first four packages under capacity 10 is 8. Some of those four packages may be skipped.

Formel til at beregne B[i][j]

• W[i], V[i] are the weight and value of package i, where i is in {1, …, n}.
• M is the maximum weight the knapsack can carry.

Base case with one package: for every capacity j ≥ W[1]:

B[1][j] = W[1]

For the general case, decide whether to include package i under capacity j:

• If package i is sprunget, B[i][j] equals the best value using packages {1, …, i-1} under capacity j:

B[i][j] = B[i - 1][j]

• If package i is taget (allowed only when W[i] ≤ j), B[i][j] equals V[i] plus the best value from packages {1, …, i-1} under capacity j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Take the larger of the two candidates.

Grundlag for dynamisk programmering

Combining the two cases gives the full recurrence:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

The base case is B[0][j] = 0 for every j, because zero packages give zero value regardless of capacity.

Beregn tabellen over muligheder

Build B using the recurrence. Once B is filled, the same table drives the trace-back that reconstructs the chosen packages. Table B has n + 1 rows and M + 1 columns:

• Row 0 is the base case, filled with zeros.
• Use row 0 to compute row 1, row 1 to compute row 2, and continue until row n is complete.

Tabel over muligheder

Trace

Once B is complete, focus on B[n][M], the optimal total value across all n packages with capacity M.

• If B[n][M] = B[n-1][M], package n was not selected, so continue tracing from B[n-1][M].
• If B[n][M] ≠ B[n-1][M], package n was selected, so continue tracing from B[n-1][M – W[n]].

Repeat until you reach row 0 of the table.

Algoritme til at slå op i oversigten over muligheder for at finde de valgte pakker

Note: whenever B[i][j] = B[i-1][j], package i is not selected. The value B[n][M] is the optimal total value packed into the knapsack.

Trin til tracing the chosen packages:

• Trin 1: Start at i = n, j = M.
• Trin 2: Scan column j from bottom up until you find a row i where B[i][j] > B[i-1][j]. Mark package i as selected: Select[i] = true.
• Trin 3: Update j = j – W[i]. If j > 0, return to Step 2, otherwise go to Step 4.
• Trin 4: Print every package marked selected.

Java Code

Følgende Java method fills B[][] bottom-up, prints the table for inspection, and then traces the selected packages.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Funktion knapsackDyProg() i Java

Forklaring af koden:

1. Allocate table B[][] and initialize every cell to 0.
2. Fill B[][] bottom-up using the recurrence from the previous section.
3. Start each cell with the “skip package i” value B[i-1][j].
4. If picking package i is feasible and gives a strictly better value, overwrite the cell.
5. Trace the selected items from row n back to row 0.
6. Whenever package n is chosen, decrement the remaining capacity by W[n-1].

Rettelse af bemærkning: the original snippet mutated parameter M while still reading B[n][M]. The safer version above uses a separate cursor j for trace.

Java driver runs the algorithm on two worked examples:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Output for the first example:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Output for the second example:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Time and Space Complexity of 0/1 Knapsack

• Tidskompleksitet: O(n · M) — the two nested loops sweep n items across M+1 capacity states.
• Rumkompleksitet: O(n · M) for the full table, reducible to O(M) by keeping only the previous row when trace-back is not needed.

The runtime is pseudo-polynomial: polynomial in the value of M but exponential in the bits used to encode M. That is why 0/1 Knapsack remains NP-hard even though Dynamic Programming is efficient in practice.

Applications of the 0/1 Knapsack Problem

• Cargo loading, container packing, and warehouse picking under weight limits.
• Budget allocation across investment projects with fixed cost and expected return.
• Cutting-stock problems in manufacturing that cannot split individual pieces.
• Cryptography schemes such as Merkle-Hellman that build on knapsack hardness.
• Resource-constrained scheduling in cloud computing and CPU task placement.
• Feature selection in machine learning under a fixed feature budget.

Ofte Stillede Spørgsmål