数学建模(4)动态规划模型

动态规划模型^[1]

背包问题

【例 4】假设张三要去野营，他准备了以下物品：

物品	重量(斤)	价值
水	3	10
书	1	3
食物	2	9
小刀	3	4
衣物	2	5
手机	1	10

每样东西都有相应的价值，可呆呆的他在收拾背包时发现，他的背包 最大容量只有 6 斤，装不下所有的东西，只能从这堆东西中挑选组合价值最高的物品。

def dynamic_p() -> list:
    items = [
        {"name": "水", "weight": 3, "value": 10},
        {"name": "书", "weight": 1, "value": 3},
        {"name": "食物", "weight": 2, "value": 9},
        {"name": "小刀", "weight": 3, "value": 4},
        {"name": "衣物", "weight": 2, "value": 5},
        {"name": "手机", "weight": 1, "value": 10}
    ]
    max_capacity = 6  # 约束条件为背包最大承重6
    dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]

    for row in range(1, len(items) + 1):  # row代表行
        for col in range(1, max_capacity+1):  # col代表列
            weight = items[row-1]["weight"]  # 获取当前物品重量
            value = items[row-1]["value"]  # 获取当前物品价值
            if weight > col:  # 判断物品重量是否大于当前背包容量
                dp[row][co1] = dp[row-1][col]  # 大于直接取上一次最优结果此时row-1代表上一行
            else:
                # 使用内置函数max()，将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
                dp[row][col] = max(value+dp[row-1][col-weight], dp[row-1][col])
    return dp

dp = dynamic_p()
for i in dp:  # 打印数组
    print(i)
print(dp[-1][-1])  # 打印最优解的价值和

• 输出：

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 10, 10, 10, 10]
[0, 3, 3, 10, 13, 13, 13]
[0, 3, 9, 12, 13, 19, 22]
[0, 3, 9, 12, 13, 19, 22]
[0, 3, 9, 12, 14, 19, 22]
[0, 10, 13, 19, 22, 24, 29]
29

参考文献

1. 司守奎，孙玺菁. 数学建模算法与应用(第 3 版). ↩︎