Bài toán cái ba lô 0-1 (0-1 Knapsack Problem) trong C

Cái ba lô là túi. Bài toán cái ba lô đặt vật vào túi dựa trên giá trị vật, mục tiêu tối đa hóa giá trị trong túi. Trong 0-1 Knapsack, hoặc bỏ vật vào, hoặc loại bỏ, không cho phép lấy một phần vật.

Ví dụ bài toán

Gia tri vat = {20, 25, 40}
Trong luong vat = {25, 20, 30}
Dung luong tui = 50

Phân phối trọng lượng

25,20 {1,2}
20,30 {2,3}
Nếu dùng {1,3} trọng lượng vượt quá max.
{1,2}: trọng lượng=45, giá trị=45
{2,3}: trọng lượng=50, giá trị=65
Giá trị max = 65 -> chọn vật 2 và 3.

CHƯƠNG TRÌNH 0-1 KNAPSACK

#include <stdio.h>
int max(int a, int b) {
    if (a > b) return a;
    else return b;
}
int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int knap[n+1][W+1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                knap[i][w] = 0;
            else if (wt[i-1] <= w)
                knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
            else
                knap[i][w] = knap[i-1][w];
        }
    }
    return knap[n][W];
}
int main() {
    int val[] = {20, 25, 40};
    int wt[] = {25, 20, 30};
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printf("Giai phap: %d", knapsack(W, wt, val, n));
    return 0;
}

Kết quả

Giai phap: 65