多阶段决策问题的代码
时间: 2024-09-06 19:07:32 浏览: 105
多阶段决策问题,也称为动态规划问题,通常涉及一系列相互关联的决策,每个决策都会影响后续状态的成本或收益。在编写此类问题的代码时,我们会使用递归或迭代的方式,结合价值函数来解决。
一个简单的例子可以是“背包问题”的动态规划版本。假设我们有一个背包容量限制,需要在多个物品中选择最优组合,每件物品都有重量和价值。代码可能会这样设计:
```python
def knapsack_dp(weights, values, capacity):
dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights) + 1)]
# 动态规划核心逻辑
for i in range(1, len(weights) + 1):
for w in range(1, capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]
return dp[-1][-1]
# 示例:给定物品重量和价值,以及背包容量
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
optimal_value = knapsack_dp(weights, values, capacity)
```
在这个例子中,`dp` 数组表示了在每个状态(背包容量从 0 到当前所有物品的总重量)下可以获得的最大价值。通过比较包含当前物品和不包含当前物品两种情况,找到最优解。