大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
动态规划之01背包问题及其优化(python实现)
**背包问题(**Knapsack problem)是一种组合优化的NP完全问题。
问题描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
解决思路:动态规划,对每一件物品遍历背包容量,当背包可容纳值大于等于当前物品,与之前已放进去的物品所得价值进行对比,考虑是否需要置换。
递归定义如下:
python实现算法如下:
def bag(n, c, w, v):
""" 测试数据: n = 6 物品的数量, c = 10 书包能承受的重量, w = [2, 2, 3, 1, 5, 2] 每个物品的重量, v = [2, 3, 1, 5, 4, 3] 每个物品的价值 """
# 置零,表示初始状态
value = [[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):
value[i][j] = value[i - 1][j]
# 背包总容量够放当前物体,遍历前一个状态考虑是否置换
if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
for x in value:
print(x)
return value
输入测试数据结果如下:最大价值为15
接下来,输出背包里所放的物品,只需从尾遍历物品,当value大于上一行同样位置的value时,表示放进该物品
代码如下:
def show(n, c, w, value):
print('最大价值为:', value[n][c])
x = [False for i in range(n)]
j = c
for i in range(n, 0, -1):
if value[i][j] > value[i - 1][j]:
x[i - 1] = True
j -= w[i - 1]
print('背包中所装物品为:')
for i in range(n):
if x[i]:
print('第', i+1, '个,', end='')
输出结果:
以上时间复杂度为O(cn),已经不能再优化了。但空间复杂度O(cn)可以优化为O(c)。
思路:尾部迭代,每个状态表示上一次的最佳结果。
实现代码如下;
def bag1(n, c, w, v):
values = [0 for i in range(c+1)]
for i in range(1, n + 1):
for j in range(c, 0, -1):
# 背包总容量够放当前物体,遍历前一个状态考虑是否置换,这里的value[j]即为上一次最佳结果
if j >= w[i-1]:
values[j] = max(values[j-w[i-1]]+v[i-1], values[j])
return values
完整代码:
#coding:utf-8
def bag(n, c, w, v):
""" 测试数据: n = 6 物品的数量, c = 10 书包能承受的重量, w = [2, 2, 3, 1, 5, 2] 每个物品的重量, v = [2, 3, 1, 5, 4, 3] 每个物品的价值 """
# 置零,表示初始状态
value = [[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):
value[i][j] = value[i - 1][j]
# 背包总容量够放当前物体,遍历前一个状态考虑是否置换
if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
for x in value:
print(x)
return value
def show(n, c, w, value):
print('最大价值为:', value[n][c])
x = [False for i in range(n)]
j = c
for i in range(n, 0, -1):
if value[i][j] > value[i - 1][j]:
x[i - 1] = True
j -= w[i - 1]
print('背包中所装物品为:')
for i in range(n):
if x[i]:
print('第', i+1, '个,', end='')
def bag1(n, c, w, v):
values = [0 for i in range(c+1)]
for i in range(1, n + 1):
for j in range(c, 0, -1):
# 背包总容量够放当前物体,遍历前一个状态考虑是否置换
if j >= w[i-1]:
values[j] = max(values[j-w[i-1]]+v[i-1], values[j])
return values
if __name__ == '__main__':
n = 6
c = 10
w = [2, 2, 3, 1, 5, 2]
v = [2, 3, 1, 5, 4, 3]
value = bag(n, c, w, v)
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2]
# [0, 0, 3, 3, 5, 5, 5, 5, 5, 5, 5]
# [0, 0, 3, 3, 5, 5, 5, 6, 6, 6, 6]
# [0, 5, 5, 8, 8, 10, 10, 10, 11, 11, 11]
# [0, 5, 5, 8, 8, 10, 10, 10, 12, 12, 14]
# [0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]
show(n, c, w, value)
# 最大价值为: 15
# 背包中所装物品为:
# 第 2 个,第 4 个,第 5 个,第 6 个,
print('\n空间复杂度优化为N(c)结果:', bag1(n, c, w, v))
#空间复杂度优化为N(c)结果: [0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]
如有错误,欢迎指正和交流~
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164409.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...