01背包问题的动态规划算法代码及伪代码

动态规划是一种解决最优化问题的算法思想。01背包问题就是其中的经典例子之一。下面是01背包问题的动态规划算法代码及伪代码。

伪代码：

1.输入数据：物品的数量n，背包的容量C，每个物品的重量w[i]和价值v[i]。

2.定义二维数组dp[i][j]，表示在前i个物品中选择若干个物品放入容量为j的背包中所能获得的最大价值。

3.初始化dp数组：dp[0][j]=0 (0<=j<=C)，dp[i][0]=0 (1<=i<=n)。

4.状态转移方程：

当j>=w[i]时，dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]) //放入第i件物品

当j<w[i]时，dp[i][j]=dp[i-1][j] //不放第i件物品

5.最终结果：dp[n][C]即为所求。

代码实现（C++）：

int knapsack(int n, int C, int w[], int v[]) {
    int dp[n+1][C+1];
    memset(dp, 0, sizeof(dp));  //初始化为0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][C];
}

其中，n表示物品的数量，C表示背包的容量，w[]和v[]分别表示每个物品的重量和价值。函数返回值为最大价值。