0-1背包问题动态规划模型的Python解法

世界尽头与你 2022-09-09 03:15:55 阅读数:653

问题动态规划背包0-1

0-1背包问题动态规划模型的Python解法

1.01背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V

01背包即每种物品的数量为1,可以选择放或者不放


2.Python解决方案

算法代码:

import numpy as np
# 0-1背包算法
def knapsack(v, w, n, capacity):
i = 0
capacity = capacity + 1 # 初始化背包容量最大值
m = np.zeros((n, capacity)) # 初始化
x = np.zeros(n)
for i in range(n):
for j in range(capacity):
if (j >= w[i]):
m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
else:
m[i][j] = m[i - 1][j]
print('动态规划装载表:\n', m)
capacity = capacity - 1
for i in range(n - 1, 0, -1):
if (m[i][capacity] == m[i - 1][capacity]):
x[i] = 0
else:
x[i] = 1
capacity -= w[i]
x[0] = 1 if (m[1][capacity] > 0) else 0
weight = 0
value = 0
print('装载的物品编号为:')
for i in range(len(x)):
if (x[i] == 1):
weight = weight + w[i]
value = value + v[i]
print(' ', i + 1)
print('装载的物品重量为:')
print(weight)
print('装入的物品价值为:')
print(value)
return m
file_name = ['input_assgin02_01.dat', 'input_assgin02_02.dat', 'input_assgin02_03.dat',
'input_assgin02_04.dat', 'input_assgin02_05.dat']
# 循环读取文件数据
for file_name in file_name:
a = np.loadtxt(file_name)
n = int(a[0][0]) # 读取物品数量
capacity = int(a[0][1])
print('--------------------------------------------------------------------------------------------------')
print('{0}文件中的测试结果:'.format(file_name))
print('物品数量为:\n', n, '\n背包载重量为:\n', capacity)
w = [0] * n # 初始化物品重量列表
value = [0] * n # 初始化物品价值列表
a = np.loadtxt(file_name, skiprows=1, dtype=int)
for i in range(n):
w[i] = int(a[i][0]) # 读取物品重量列表
value[i] = int(a[i][1]) # 读取物品价值列表
print('物品的重量列表为:\n', w, '\n物品的价值列表为:\n', value)
knapsack(value, w, n, capacity)

数据文件,以input_assgin02_01.dat文件为例:

5 10
2 6
2 3
6 5
5 4
4 6

第一行的5和10分别是物品数量和背包载重量

随后的5行为物品的重量和价值

程序会得出动态规划装载表及最终的运算结果:

--------------------------------------------------------------------------------------------------
input_assgin02_01.dat文件中的测试结果:
物品数量为:
5
背包载重量为:
10
物品的重量列表为:
[2, 2, 6, 5, 4]
物品的价值列表为:
[6, 3, 5, 4, 6]
动态规划装载表:
[[ 0. 0. 6. 6. 6. 6. 6. 6. 6. 6. 6.]
[ 0. 0. 6. 6. 9. 9. 9. 9. 9. 9. 9.]
[ 0. 0. 6. 6. 9. 9. 9. 9. 11. 11. 14.]
[ 0. 0. 6. 6. 9. 9. 9. 10. 11. 13. 14.]
[ 0. 0. 6. 6. 9. 9. 12. 12. 15. 15. 15.]]
装载的物品编号为:
1
2
5
装载的物品重量为:
8
装入的物品价值为:
15

3.01背包问题例题

在这里插入图片描述

版权声明:本文为[世界尽头与你]所创,转载请带上原文链接,感谢。 https://blog.csdn.net/Gherbirthday0916/article/details/126770799