编辑代码

#include <stdio.h>

// 输入：物品的重量和价值数组、背包容量
// 输出：最大价值
int knapSack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0)
        return 0;

    // 如果物品的重量大于背包容量，不包含此物品
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);

    // 返回包含和不包含第n个物品时价值的最大值
    else
        return max(
            val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
            knapSack(W, wt, val, n - 1)
        );
}

// 辅助函数来比较两个数的最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int val[] = {60, 100, 120};   // 物品的价值
    int wt[] = {10, 20, 30};      // 物品的重量
    int W = 50;                   // 背包的容量
    int n = sizeof(val) / sizeof(val[0]); // 物品的数量
    printf("%d\n", knapSack(W, wt, val, n));
    return 0;
}