0-1背包问题c语言代码

0-1背包问题是动态规划的经典问题之一，目标是在给定的一组物品（每个物品有自己的价值和重量）中选择一些放入背包，使得背包的总重量不超过限制，并且总价值最大。以下是用C语言实现的一个简单版本：

#include <stdio.h>

int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n + 1][W + 1];

    // 初始化二维数组
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i - 1] <= w)
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50, wt[] = {10, 20, 30}, val[] = {60, 100, 120};
    int n = sizeof(wt) / sizeof(wt[0]);

    printf("The maximum value that can be put in the knapsack is %d", knapsack(W, wt, val, n));

    return 0;
}

这个代码首先定义了一个二维数组`dp`来保存子问题的解，然后通过两层循环遍历所有可能的情况。如果当前物品的重量小于等于背包容量，那么有两种选择：包含该物品或者不包含。最后，在main函数中定义了背包的容量、物品的重量和价值数组，调用knapsack函数并打印结果。