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

2022-09-09 03:17:01

# 1.01背包问题

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 = 1 if (m[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:
n = int(a)  # Read the number of items
capacity = int(a)
print('--------------------------------------------------------------------------------------------------')
print('{0}Test results in file：'.format(file_name))
print('物品数量为：\n', n, '\nThe load capacity of the backpack is ：\n', capacity)
w =  * n  # Initialize the item weight list
value =  * 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])  # Read a list of item weights
value[i] = int(a[i])  # 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)
``````

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

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 