0/1 Problemă la rucsac Remediere folosind un exemplu de programare dinamică

Care este problema rucsacului?

Problemă la rucsac 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?

Intrare:

• Greutatea maximă M și numărul de pachete n.
• Matrice de greutate W[i] și valoarea corespunzătoare V[i].

ieșire:

• 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.
• Problema rucsacului fracționat solved by a Greedy Strategy. Here you may take a fraction of any package to fill the remaining capacity.

Cum se rezolvă problema rucsacului folosind programarea dinamică cu exemplu

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.

Rezolvați problema rucsacului folosind programarea dinamică

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.

Analizați problema rucsacului 0/1

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.

• Răspunsul final este 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.

Formula pentru a calcula 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 omit, 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 luate (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.

Baza programării dinamice

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.

Calculați tabelul de opțiuni

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 de Opțiuni

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.

Algoritm pentru a căuta tabelul de opțiuni pentru a găsi pachetele selectate

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.

Pași pentru tracing the chosen packages:

• Pasul 1: Start at i = n, j = M.
• Pasul 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.
• Pasul 3: Update j = j – W[i]. If j > 0, return to Step 2, otherwise go to Step 4.
• Pasul 4: Print every package marked selected.

Java Code

Următoarele 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--;
    }
}

Funcția knapsackDyProg() în Java

Explicația codului:

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].

Notă de corecție: the original snippet mutated parameter M while still reading B[n][M]. The safer version above uses a separate cursor j pentru 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

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

Timpul de rulare este 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.

Întrebări frecvente