动态规划示例,python代码,直接写代码
时间: 2023-01-31 22:06:55 浏览: 80
好的,下面是一个用动态规划求解背包问题的例子。在这个例子中,我们有一个背包,容量为C,有n个物品,每个物品都有一个体积和价值。我们的目标是在不超过背包容量的情况下,选择物品,使得总价值最大。
下面是用 Python 实现的代码:
```
def knapsack(C, n, w, v):
# 初始化状态数组
dp = [[0] * (C + 1) for _ in range(n + 1)]
# 进行状态转移
for i in range(1, n + 1):
for j in range(1, C + 1):
if j >= w[i - 1]:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][C]
# 测试
C = 10
n = 5
w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]
print(knapsack(C, n, w, v)) # 输出结果应该是 15
```
在这个例子中,C 表示背包的容量,n 表示物品的数量,w 和 v 分别表示每个物品的体积和价值。
算法的核心部分在于状态转移方程:
```
if j >= w[i - 1]:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
else:
dp[i][j] = dp[i - 1][j]
```
这个方程的意思是:如果当前背包的容量大于等于当前物品的体积