编辑代码

#include <stdio.h>

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

int knapsack(int W, int weights[], int values[], int n) {
    int i, w;
    int K[n + 1][W + 1];

    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (weights[i - 1] <= w)
                K[i][w] = max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }

    return K[n][W];
}

int main() {
    printf("测试1：");
    int capacity1 = 10;
    int weights1[] = {2, 3, 4, 5};
    int values1[] = {3, 4, 5, 6};
    int numItems1 = sizeof(weights1) / sizeof(weights1[0]);

    int maxValue1 = knapsack(capacity1, weights1, values1, numItems1);
    printf("可获得的最大价值: %d\n", maxValue1);


    printf("测试2：");
    int capacity2 = 15;
    int weights2[] = {5, 6, 7, 8};
    int values2[] = {3, 4, 5, 6};
    int numItems2 = sizeof(weights2) / sizeof(weights2[0]);
    int maxValue2 = knapsack(capacity2, weights2, values2, numItems2);
    printf("可获得的最大价值: %d\n", maxValue2);


    printf("测试3：");
    int capacity3 = 5;
    int weights3[] = {2, 3, 4, 5};
    int values3[] = {3, 4, 5, 6};
    int numItems3 = sizeof(weights3) / sizeof(weights3[0]);

    int maxValue3 = knapsack(capacity3, weights3, values3, numItems3);
    printf("可获得的最大价值: %d\n", maxValue3);

    return 0;
}