2023年8月1日发(作者：)

Python实现多维背包问题MKP算法（1）——动态多维背包问题描述MKP多维背包问题，特殊的背包问题，是著名的整数规划问题。要求从多个限制条件中选出满⾜所有条件的最佳组合，并计算出最优价值。解题思路对⼀个属性进⾏不超过限制条件的选择（即01背包问题的列出可能性），最后求多个属性的交集，在交集中找到最⼤价值即可。代码实现创建输⼊⽂本输⼊数据：（第⼀⾏第⼀个是商品个数，第⼆个是属性个数，第三个是计算出的最优价值；第⼆⾏是6个商品每⼀个的价值；第三⾏到倒数第⼆⾏是属性；最后⼀⾏是限制条件，最后⼀⾏第⼀个数是第⼀个属性的限制条件，第⼆是第⼆个属性的限制条件，以此类推，数据格式如下,不要有多余的空格或者空⾏。）6 10 3800100 600 1200 2400 500 20008 12 13 64 22 418 12 13 75 22 413 6 4 18 6 45 10 8 32 6 125 13 8 42 6 205 13 8 48 6 200 0 0 0 8 03 0 4 0 8 03 2 4 0 8 43 2 4 8 8 480 96 20 36 44 48 10 18 22 24输出数据：商品的个数为： 6 属性的个数为： 10价值分别为： [100.0, 600.0, 1200.0, 2400.0, 500.0, 2000.0]选择第 2 个商品 | 选择第 3 个商品 | 选择第 6 个商品 |最⼤价值为 3800.0 元import pandas #需要导⼊库import numpy #需要导⼊库import timestart = ()class MKP_Object: def allPossibility(restrict,attribute, nums): #寻找满⾜限制条件的组合 parameter1 = [[]] element = [] for i in range(nums): parameter2 = [] for j in parameter1: element=j+[i] if sum(attribute[element])

want_data = [] bestValue=[] data_1th = list(map(float, all_data[0].split())) # 切割商品数据和约束条件数据 commodity_number = int(data_1th[0]) # 读⼊商品数 constraints_numbers = int(data_1th[1]) # 读⼊约束条件数 constraints = list(map(float, all_data[int(len(all_data) - 1)].split())) # 读⼊约束条件 values = list(map(float, all_data[1].split())) # 读⼊商品的价值 cost=(values) for i in range(2, constraints_numbers + 2): want_(list(map(int, all_data[i].split()))) # 添加数据到列表中 data_array=(want_data) property=(data_array[0]) intersection=MKP_sibility(constraints[0],property,commodity_number) #计算第⼀个属性的所选商品可能性

for i in range(1,constraints_numbers): property=(data_array[i]) propertyPossibility=MKP_sibility(constraints[i],property,commodity_number) intersection=MKP_(intersection,propertyPossibility)

for i in intersection: (sum(cost[i])) #将价值之和添加进列表bestValue bestValue = (bestValue) num = (bestValue) #读取最⼤值下标 intersection = intersection[num] #获取价格最⼤值的元素 print("n") print("商品的个数为：",commodity_number," 属性的个数为：",constraints_numbers) print("价值分别为：",values) for i in range(len(intersection)): print("选择第",intersection[i]+1,end=" 个商品 | ") print("n最⼤价值为",max(bestValue),"元")end = ()print("程序运⾏时间为： ",end - start,"s")该算法借鉴了同学思路，我修改了⼤部分算法以及数据结构，修改成了⾃⼰的思路。如有想法请在评论区发表，⼀起交流学习

2023年8月1日发(作者：)

Python实现多维背包问题MKP算法（1）——动态多维背包问题描述MKP多维背包问题，特殊的背包问题，是著名的整数规划问题。要求从多个限制条件中选出满⾜所有条件的最佳组合，并计算出最优价值。解题思路对⼀个属性进⾏不超过限制条件的选择（即01背包问题的列出可能性），最后求多个属性的交集，在交集中找到最⼤价值即可。代码实现创建输⼊⽂本输⼊数据：（第⼀⾏第⼀个是商品个数，第⼆个是属性个数，第三个是计算出的最优价值；第⼆⾏是6个商品每⼀个的价值；第三⾏到倒数第⼆⾏是属性；最后⼀⾏是限制条件，最后⼀⾏第⼀个数是第⼀个属性的限制条件，第⼆是第⼆个属性的限制条件，以此类推，数据格式如下,不要有多余的空格或者空⾏。）6 10 3800100 600 1200 2400 500 20008 12 13 64 22 418 12 13 75 22 413 6 4 18 6 45 10 8 32 6 125 13 8 42 6 205 13 8 48 6 200 0 0 0 8 03 0 4 0 8 03 2 4 0 8 43 2 4 8 8 480 96 20 36 44 48 10 18 22 24输出数据：商品的个数为： 6 属性的个数为： 10价值分别为： [100.0, 600.0, 1200.0, 2400.0, 500.0, 2000.0]选择第 2 个商品 | 选择第 3 个商品 | 选择第 6 个商品 |最⼤价值为 3800.0 元import pandas #需要导⼊库import numpy #需要导⼊库import timestart = ()class MKP_Object: def allPossibility(restrict,attribute, nums): #寻找满⾜限制条件的组合 parameter1 = [[]] element = [] for i in range(nums): parameter2 = [] for j in parameter1: element=j+[i] if sum(attribute[element])

want_data = [] bestValue=[] data_1th = list(map(float, all_data[0].split())) # 切割商品数据和约束条件数据 commodity_number = int(data_1th[0]) # 读⼊商品数 constraints_numbers = int(data_1th[1]) # 读⼊约束条件数 constraints = list(map(float, all_data[int(len(all_data) - 1)].split())) # 读⼊约束条件 values = list(map(float, all_data[1].split())) # 读⼊商品的价值 cost=(values) for i in range(2, constraints_numbers + 2): want_(list(map(int, all_data[i].split()))) # 添加数据到列表中 data_array=(want_data) property=(data_array[0]) intersection=MKP_sibility(constraints[0],property,commodity_number) #计算第⼀个属性的所选商品可能性

for i in range(1,constraints_numbers): property=(data_array[i]) propertyPossibility=MKP_sibility(constraints[i],property,commodity_number) intersection=MKP_(intersection,propertyPossibility)

for i in intersection: (sum(cost[i])) #将价值之和添加进列表bestValue bestValue = (bestValue) num = (bestValue) #读取最⼤值下标 intersection = intersection[num] #获取价格最⼤值的元素 print("n") print("商品的个数为：",commodity_number," 属性的个数为：",constraints_numbers) print("价值分别为：",values) for i in range(len(intersection)): print("选择第",intersection[i]+1,end=" 个商品 | ") print("n最⼤价值为",max(bestValue),"元")end = ()print("程序运⾏时间为： ",end - start,"s")该算法借鉴了同学思路，我修改了⼤部分算法以及数据结构，修改成了⾃⼰的思路。如有想法请在评论区发表，⼀起交流学习