c语言讲解背包问题

背包问题是一个经典的动态规划问题，它的基本形式是：有一个背包，容量为C（Capacity），现在有n种不同的物品，编号为1,2,...,n，其中第i个物品的重量为w[i]，价值为v[i]。问可以向这个背包中放入哪些物品，使得在不超过背包容量的情况下，背包中物品的总价值最大。

下面是一个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) 
{
    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 (wt[i-1] <= w)
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
            else
                K[i][w] = K[i-1][w];
        }
    }
    
    return K[n][W];
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    
    printf("Max value: %d", knapsack(W, wt, val, n));
    
    return 0;
}

这里使用K[i][w]表示将前i个物品放入容量为w的背包中所获得的最大价值。根据动态规划的思想，我们可以先求出将前1个物品放入背包中的最大价值，然后依次求解将前2个、前3个、...、前n个物品放入背包中的最大价值。最终结果就是K[n][W]。

具体实现时，我们需要使用两重循环遍历所有可能的情况，并且需要注意边界条件的处理（即K[0][w]和K[i][0]都应该初始化为0）。对于第i个物品，如果它的重量小于等于当前背包的容量，那么它可以选择放入背包中，此时背包的价值就是val[i-1] + K[i-1][w-wt[i-1]]；否则它只能不放入背包中，背包的价值就是K[i-1][w]。

最终返回的结果就是K[n][W]，它表示将前n个物品放入容量为W的背包中所获得的最大价值。