大家好！今天来聊聊经典的 01背包问题 🎒✨。这是一道算法入门中的必修课，非常适合用来锻炼动态规划思维哦！如果还没接触过的话，别担心，下面有模板代码，简单易懂，快收藏起来吧！
首先，什么是01背包？简单来说，就是你有一个容量为 `W` 的背包，有一系列物品，每个物品有自己的重量和价值，只能选择装或不装（即“01”）。目标是让背包装入的物品总价值最大。💡
实现这个算法的核心在于状态转移方程：
`dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`
其中 `dp[i][j]` 表示前 `i` 个物品在背包容量为 `j` 时的最大价值。
下面是简洁的 Python 模板代码👇：
```python
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] (W+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(W+1):
if j >= weights[i-1]:
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]
示例调用
weights = [2, 3, 4]
values = [3, 4, 5]
W = 5
print(knapsack(weights, values, W)) 输出：7
```
通过这段代码，你可以轻松解决类似问题啦！🌟 如果觉得有用，记得点赞支持哦~ 😊
免责声明：本文由用户上传，如有侵权请联系删除！
