0/1 แก้ไขปัญหากระเป๋าเป้สะพายหลังโดยใช้ตัวอย่างการเขียนโปรแกรมแบบไดนามิก

ปัญหากระเป๋าเป้สะพายหลังคืออะไร?

การขอ ปัญหากระเป๋าเป้สะพายหลัง 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:

• น้ำหนักสูงสุด M และจำนวนบรรจุภัณฑ์ n
• อาร์เรย์ของน้ำหนัก W[i] และค่าที่สอดคล้องกัน 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.
• ปัญหาเป้แบบเศษส่วน solved by a Greedy Strategy. Here you may take a fraction of any package to fill the remaining capacity.

วิธีแก้ปัญหากระเป๋าเป้สะพายหลังโดยใช้การเขียนโปรแกรมแบบไดนามิกพร้อมตัวอย่าง

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.

แก้ปัญหากระเป๋าเป้สะพายหลังโดยใช้การเขียนโปรแกรมแบบไดนามิก

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

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.

สูตรคำนวณ 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 ข้าม, 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 นำ (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.

พื้นฐานของการเขียนโปรแกรมแบบไดนามิก

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.

คำนวณตารางตัวเลือก

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.

ตารางตัวเลือก

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.

อัลกอริทึมในการค้นหาตารางตัวเลือกเพื่อค้นหาแพ็คเกจที่เลือก

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.

ขั้นตอนสำหรับ tracing the chosen packages:

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

Java Code

ดังต่อไปนี้ 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--;
    }
}

ฟังก์ชัน knapsackDyProg() ใน Java

คำอธิบายของรหัส:

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

หมายเหตุการแก้ไข: the original snippet mutated parameter M while still reading B[n][M]. The safer version above uses a separate cursor j สำหรับ 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

• ความซับซ้อนเชิงเวลา: O(n · M) — the two nested loops sweep n items across M+1 capacity states.
• ความซับซ้อนของพื้นที่: 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.

คำถามที่พบบ่อย