C语言实现背包算法：代码示例与详解

下面是使用C语言实现背包算法的例子：

#include <stdio.h>

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

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);
    } else {
        return max(val[n-1] + knapsack(W-wt[n-1], wt, val, n-1), knapsack(W, wt, val, n-1));
    }
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("Maximum value that can be put in a knapsack of capacity %d is %d\n", W, knapsack(W, wt, val, n));
    return 0;
}

该算法接受一个数组'val'和一个数组'wt'，分别表示物品的价值和重量。它还接受一个整数'W'，表示背包的最大容量。使用递归方式，该算法计算出可以放入背包中的最大价值。

该算法首先检查如果没有物品或者背包容量为零，则返回零。否则，如果最后一个物品的重量大于背包容量，则递归调用函数，排除最后一个物品。否则，算法将计算包括最后一个物品的最大价值和不包括最后一个物品的最大价值中的较大值。