0/1背包问题的伪代码

以下是 0/1 背包问题的伪代码：

// 输入：
// - w: 物品重量数组
// - v: 物品价值数组
// - W: 背包容量
// 输出：最大价值

function knapsack(w, v, W):
    n = w.length
    // dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
    dp = new Array(n+1).fill(0).map(() => new Array(W+1).fill(0))

    for i from 1 to n:
        for j from 1 to W:
            if j < w[i-1]:
                // 背包容量不足，无法装入第 i 个物品
                dp[i][j] = dp[i-1][j]
            else:
                // 能够装入第 i 个物品，考虑是否放入背包
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])

    return dp[n][W]

其中 `max(a, b)` 返回 `a` 和 `b` 中的较大值。

相关问题

蛮力法0/1背包问题伪代码

蛮力法（Brute Force）是一种暴力枚举的算法，它通过枚举所有可能的解来寻找最优解。对于0/1背包问题，蛮力法的伪代码如下：

1. 初始化最大价值为0
2. 枚举所有可能的物品组合：
a. 对于每个物品，可以选择放入或不放入背包
b. 对于每种组合，计算其总重量和总价值
c. 如果总重量不超过背包容量且总价值大于当前最大价值，则更新最大价值
3. 返回最大价值

需要注意的是，蛮力法的时间复杂度为O(2^n)，其中n为物品数量，因此对于大规模的问题，蛮力法的效率非常低下。

动态规划法求解0/1背包问题的伪代码

以下是动态规划法求解0/1背包问题的伪代码：

1. 初始化一个二维数组dp[n+1][W+1]，其中n为物品数量，W为背包容量
2. 将dp[0][j]（0<=j<=W）和dp[i][0]（0<=i<=n）都初始化为0
3. for i in range(1, n+1):
       for j in range(1, W+1):
           if w[i] > j:
               dp[i][j] = dp[i-1][j]
           else:
               dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
4. 返回dp[n][W]作为最优解

其中，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。在第3步中，如果第i个物品的重量大于当前背包容量j，则无法放入，直接继承上一个状态的最优解；否则，需要比较放入和不放入第i个物品的价值大小，取最大值作为当前状态的最优解。