0-1背包问题的动态规划算法实现c

0-1背包问题是一个经典的动态规划问题，其动态规划算法实现可以用C语言来实现。以下是一个简单的实现代码：

#include <iostream>
using namespace std;

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[] = {6, 3, 5, 4, 6};
    int wt[] = {2, 2, 6, 5, 4};
    int W = 10;
    int n = sizeof(val) / sizeof(val[0]);
    cout << "背包最大价值是：" << knapSack(W, wt, val, n) << endl;
    return 0;
}

该算法的时间复杂度为O(nW)，其中n是物品数量，W是背包容量。在实现中，我们使用一个二维数组K来存储每个子问题的最优解，其中K[i][w]表示前i个物品放入容量为w的背包中所能获得的最大价值。在计算K[i][w]时，我们需要考虑两种情况：将第i个物品放入背包中和不将第i个物品放入背包中。如果将第i个物品放入背包中，则最大价值为val[i-1] + K[i-1][w-wt[i-1]]，否则最大价值为K[i-1][w]。最终，我们返回K[n][W]作为问题的最优解。