请利用动态规划求解0-1背包问题。0-1背包问题是说,已知n个物品,每个物品的重量和价值均为已知的正实数,给定一个背包,要选择一些物品放入背包,约束条件是放入背包的物品的重量之和不超过已知的上限C(C是一个给定的正实数),目的是使得放入背包的物品的价值和最大。 代码
时间: 2023-06-13 18:03:16 浏览: 118
0-1背包问题(动态规划)
5星 · 资源好评率100%
以下是0-1背包问题的动态规划实现代码:
```python
def knapsack_01(C, w, v):
n = len(w)
dp = [[0 for j in range(C + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, C + 1):
if w[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
return dp[n][C]
```
其中,C是背包的容量,w和v分别是物品的重量和价值,n是物品的数量。dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。动态规划的状态转移方程如下:
$$
dp[i][j] = \begin{cases}
0, & i = 0 \text{ or } j = 0 \\
dp[i-1][j], & w_i > j \\
\max(dp[i-1][j], dp[i-1][j-w_i]+v_i), & w_i \leq j
\end{cases}
$$
最终返回dp[n][C],即前n个物品放入容量为C的背包中所能获得的最大价值。
阅读全文