0-1 Knapsack Problem ในภาษา C

0-1 Knapsack: มีกระเป๋าสัมภาระน้ำหนักสูงสุด W และของ n ชิ้น แต่ละชิ้นมีน้ำหนัก wt[i] และค่า val[i] ตัดสินใจเอาหรือไม่เอาแต่ละชิ้น (0 หรือ 1) เพื่อให้ค่ารวมมากที่สุดและน้ำหนักไม่เกิน W

ตัวอย่าง

val = {20, 25, 40}, wt = {25, 20, 30}, W = 50

เลือกชิ้นที่ 2 และ 3: น้ำหนัก 50, ค่า 65 (สูงสุด)

Dynamic Programming Solution

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[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("Max value: %d", knapsack(W, wt, val, n));
    return 0;
}

ผลลัพธ์

Max value: 65