完全背包问题动态规划c++代码

以下是完全背包问题的动态规划代码，以C语言实现：

#include <stdio.h>
#include <stdlib.h>

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

int knapsack(int W, int wt[], int val[], int n) {
    int i, j;
    int **dp = (int **)malloc((n + 1) * sizeof(int *));
    for (i = 0; i < n + 1; i++) {
        dp[i] = (int *)malloc((W + 1) * sizeof(int));
    }

    for (i = 0; i < n + 1; i++) {
        for (j = 0; j < W + 1; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else if (wt[i - 1] <= j) {
                dp[i][j] = max(val[i - 1] + dp[i][j - wt[i - 1]], dp[i - 1][j]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    int result = dp[n][W];

    for (i = 0; i < n + 1; i++) {
        free(dp[i]);
    }
    free(dp);

    return result;
}

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 obtained: %d", knapsack(W, wt, val, n));
    return 0;
}

在此代码中，我们使用二维数组dp[i][j]来存储在前i个物品中，容量为j的背包中最大价值。我们首先初始化dp数组的第一行和第一列为0，因为当容量为0或没有物品可选时，背包中的最大价值为0。然后，我们使用以下公式计算dp数组中的每个值：

if (wt[i - 1] <= j) {
    dp[i][j] = max(val[i - 1] + dp[i][j - wt[i - 1]], dp[i - 1][j]);
}
else {
    dp[i][j] = dp[i - 1][j];
}

如果第i个物品的重量小于或等于当前背包容量j，则该物品可选。因此，我们将第i个物品的价值val[i-1]加上剩余容量j-wt[i-1]的最大价值dp[i][j-wt[i-1]]，即可得到当前容量下的最大价值。如果该物品不可选，则当前最大价值为前一个物品的最大价值dp[i-1][j]。

最后，dp[n][W]中存储的即为在前n个物品中，容量为W的背包中可获得的最大价值。

此代码的时间复杂度为O(nW)，其中n为物品数量，W为背包容量。