动态规划代码

angetenar / 2023-08-21 / 原文

当参加数学建模竞赛时，动态规划是一个常用的解题方法。以下是一个基于动态规划的背包问题代码示例：

def knapsack_problem(weights, values, capacity):
    n = len(weights)
    
    # 创建动态规划表格
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 填充动态规划表格
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])
    
    # 获取最优解
    optimal_solution = dp[n][capacity]
    
    # 回溯获取选取的物品列表
    selected_items = []
    i = n
    j = capacity
    while i > 0 and j > 0:
        if dp[i][j] != dp[i-1][j]:
            selected_items.append(i-1)
            i -= 1
            j -= weights[i]
        else:
            i -= 1
    
    return optimal_solution, selected_items[::-1]

# 示例输入数据
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

# 调用动态规划函数
result, items = knapsack_problem(weights, values, capacity)

# 输出结果
print("背包的最大价值:", result)
print("选取的物品列表:", items)

在上述代码中，我们解决了一个背包问题（0-1背包）。你可以根据具体问题的要求进行以下修改：

输入数据：根据具体问题，修改weights、values和capacity的值，分别表示每个物品的重量、价值和背包的容量。
2.状态转移方程：在示例代码中，使用二维表格dp来保存子问题的解。状态转移方程为：dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])。其中dp[i][j]表示前i个物品在容量为j的
背包中的最大价值。
3.获取最优解：最优解即表格中右下角dp[n][capacity]的值。
4.回溯选取的物品列表：通过回溯可以获得选取的物品列表，该部分代码将选取的物品存储在selected_items列表中。
注意，以上代码仅为动态规划求解背包问题的示例，实际问题可能需要更多的自定义代码和状态转移方程，请根据具体情况进行相应的调整。在设计状态转移方程时，需要根据问题的特点和要求，合理选择如何利用子问题的解来求得当前问题的解。