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背包问题例题
