0/1 Dinamik Programlama Örneği Kullanarak Sırt Çantası Sorununu Düzeltme

Sırt Çantası Sorunu Nedir?

MKS Sırt Çantası Sorunu 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?

Giriş:

• Maksimum ağırlık M ve paket sayısı n.
• Ağırlık dizisi W[i] ve karşılık gelen değer V[i].

Çıktı:

• 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 Sırt Çantası Problemi solved by Dynamic Programming. Each package is either taken whole or left behind — no fractional pieces and no duplicates.
• Kesirli Sırt Çantası Problemi solved by a Greedy Strategy. Here you may take a fraction of any package to fill the remaining capacity.

Örnekle Dinamik Programlama Kullanılarak Sırt Çantası Sorunu Nasıl Çözülür

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.

Dinamik Programlamayı Kullanarak Sırt Çantası Sorununu Çözme

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.

0/1 Sırt Çantası Problemini Analiz Edin

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.

• Son cevap 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.

B[i][j]'yi Hesaplayacak Formül

• 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 atlanan, 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 alınan (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.

Dinamik Programlamanın Temelleri

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.

Seçenekler Tablosunu Hesaplayın

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.

Seçenekler Tablosu

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.

Seçilen Paketleri Bulmak İçin Seçenekler Tablosunu Arama Algoritması

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.

İçin adımlar tracing the chosen packages:

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

Java Code

Aşağıdaki 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--;
    }
}

Sırt çantasıDyProg() işlevi Java

Kodun açıklaması:

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

Düzeltme notu: the original snippet mutated parameter M while still reading B[n][M]. The safer version above uses a separate cursor j için trace.

MKS 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

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

çalışma zamanı 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.

SSS