C++用动态规划法编程实现0-1背包问题可实现代码

您好，关于您的问题，以下是用动态规划法编写实现0-1背包问题的代码示例：

#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, 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("Maximum value for 0-1 knapsack problem is: %d", knapSack(W, wt, val, n));
    return 0;
}

该代码通过动态规划法，使用二维数组K[i][w]来存储背包容积为w时，前i个物品可获得的最大价值。具体实现方法为：对于第i个物品，如果它的重量wt[i-1]小于等于当前背包容积w，那么它可以加入背包，所获得的价值为val[i-1]，再加上背包容积为w-wt[i-1]的情况下前i-1个物品可获得的最大价值K[i-1][w-wt[i-1]]，此时总价值即为K[i-1][w-wt[i-1]]+val[i-1]。否则，第i个物品无法放入背包，此时背包容积为w的情况下前i个物品可获得的最大价值即为K[i-1][w]。

希望能对您有所帮助！