dp-01背包

01背包问题是动态规划中的一个经典问题，通常用于解决资源分配问题。问题描述如下：

假设有一个背包，其最大承重为 $ W )。同时，有 $ n ) 个物品，每个物品有一个重量 $ w_i ) 和一个价值 $ v_i )。目标是选择一些物品放入背包，使得在不超过背包承重的前提下，背包中物品的总价值最大。

问题特点

• 01性质：每个物品要么选择放入背包（1），要么不放入背包（0），不能选择部分放入或多次放入。

动态规划解法

动态规划（Dynamic Programming, DP）是解决01背包问题的常用方法。我们可以通过构建一个二维数组 $ dp ) 来记录状态，其中 $ dp[i][j] ) 表示前 $ i ) 个物品在总重量不超过 $ j ) 的情况下可以获得的最大价值。

状态转移方程

• 如果不选择第 $ i ) 个物品，则 $ dp[i][j] = dp[i-1][j] )。
• 如果选择第 $ i ) 个物品，则 $ dp[i][j] = dp[i-1][j-w_i] + v_i )，前提是 $ j geq w_i )。

因此，状态转移方程可以写成：
[ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i) ]

初始化

• $ dp[0][j] = 0 $ 表示没有物品时，无论背包容量是多少，最大价值都是0。
• $ dp[i][0] = 0 $ 表示背包容量为0时，无论有多少物品，最大价值都是0。

填表过程

从 $i = 1$ 到 $ n $ 和 $ j = 0 $ 到 $ W $ 依次填表，最终 $ dp[n][W] $ 就是所求的最大价值。

空间优化

由于每次计算 $dp[i][j]$只依赖于$dp[i-1][j]$和$dp[i-1][j-w_i]$，因此可以将二维数组优化为一维数组。优化后的状态转移方程为：
[dp[j]=max(dp[j],dp[j-w_i]+v_i)]

需要注意的是，在更新$dp[j])时，$j)需要从$W)递减到$w_i)，以保证每个物品只被选择一次。

代码实现

以下是01背包问题的Python代码实现：

def knapsack(W, weights, values):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[W]

总结

01背包问题通过动态规划的方法，可以在多项式时间内解决。通过构建状态转移方程和优化空间复杂度，可以高效地求解背包问题。