背包问题动态规划法用c语言写伪代码以及代码

背包问题动态规划法伪代码：

// 物品个数为n，背包容量为W
// weights数组存储每个物品的重量，values数组存储每个物品的价值
// dp[i][j]表示前i个物品，背包容量为j时的最大价值
for i = 0 to n
    for j = 0 to W
        if i == 0 or j == 0
            dp[i][j] = 0
        else if weights[i-1] <= j
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        else
            dp[i][j] = dp[i-1][j]
return dp[n][W]

背包问题动态规划法C语言代码：

int knapsack(int W, int weights[], int values[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (weights[i-1] <= j)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][W];
}