Python solution of dynamic programming model of 0-1 knapsack problem

The end of the world with you 2022-09-09 03:17:01 阅读数:223

pythonsolutiondynamicprogrammingmodel

0-1A dynamic programming model for the knapsack problemPython解法

1.01背包问题

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

01The backpack is the quantity of each item1,可以选择放或者不放


2.Python解决方案

算法代码:

import numpy as np
# 0-1背包算法
def knapsack(v, w, n, capacity):
i = 0
capacity = capacity + 1 # Initialize the maximum knapsack capacity
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('Dynamic programming load table:\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('The loaded item number is :')
for i in range(len(x)):
if (x[i] == 1):
weight = weight + w[i]
value = value + v[i]
print(' ', i + 1)
print('The weight of the loaded item is :')
print(weight)
print('The loaded item value is :')
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]) # Read the number of items
capacity = int(a[0][1])
print('--------------------------------------------------------------------------------------------------')
print('{0}Test results in file:'.format(file_name))
print('物品数量为:\n', n, '\nThe load capacity of the backpack is :\n', capacity)
w = [0] * n # Initialize the item weight list
value = [0] * n # Initialize a list of item values
a = np.loadtxt(file_name, skiprows=1, dtype=int)
for i in range(n):
w[i] = int(a[i][0]) # Read a list of item weights
value[i] = int(a[i][1]) # Read the item value list
print('The weight list for the item is :\n', w, '\nThe item's value list is :\n', value)
knapsack(value, w, n, capacity)

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

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

第一行的5和10are the number of items and the load capacity of the backpack, respectively

随后的5The weight and value of the behavioral item

The program will obtain the dynamic programming load table and the final operation result:

--------------------------------------------------------------------------------------------------
input_assgin02_01.datTest results in file:
物品数量为:
5
The load capacity of the backpack is :
10
The weight list for the item is :
[2, 2, 6, 5, 4]
The item's value list is :
[6, 3, 5, 4, 6]
Dynamic programming load table:
[[ 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.]]
The loaded item number is :
1
2
5
The weight of the loaded item is :
8
The loaded item value is :
15

3.01Example of the knapsack problem

在这里插入图片描述

版权声明:本文为[The end of the world with you]所创,转载请带上原文链接,感谢。 https://pythonmana.com/2022/252/202209090315386705.html