编辑代码

#include <stdio.h>

#define N 4 // 物品数量
#define W 5 // 背包容量

typedef struct {
    int weight;
    int value;
} Item;

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

int knapsack(Item items[], int n, int capacity, int current) {
    if (current == n || capacity == 0)
        return 0;

    if (items[current].weight > capacity)
        return knapsack(items, n, capacity, current + 1);

    // 不选择当前物品
    int withoutCurrent = knapsack(items, n, capacity, current + 1);

    // 选择当前物品
    int withCurrent = items[current].value +
                     knapsack(items, n, capacity - items[current].weight, current + 1);

    return max(withoutCurrent, withCurrent);
}

int main() {
    Item items[N] = {{2, 12}, {1, 10}, {3, 20}, {2, 15}};
    int totalValue = knapsack(items, N, W, 0);
    printf("%d\n", totalValue);
    return 0;
}