部分背包问题

本节学习解决部分背包问题,部分背包代表物品可以按照一定比例被分割,而后放入背包内.这是十分经典的用贪心算法解决的问题.

问题描述:

给定一些物品,用matrix表示各个物品的属性,第一项表示物品的质量,第二项表示物品的总价值.现有一背包最大承重为M,试求如何让背包中所装物品价值最高

思路解析:

既然背包中的物品可以被分割,而背包容量有限,要想让背包中所装物品价值最大,是要尽可能先装入单位价值大的物品,变量定义如下:

matrix变量:表示给定的各个物品的重量和价值

max变量:表示给定的背包所能承受的最大重量

re变量:表示背包物品的价值之和

re_list变量:表示各个物品放入的百分比,若将某一物品全部放入,则为1

完整代码如下:

def bag(matrix, max):# 初始化总价值为0re = 0# 创建一个列表，用于记录每个物品是否被选中，初始化为0re_list = [0 for _ in range(len(matrix))]# 根据物品的价值重量比对matrix进行降序排序matrix.sort(key=lambda x: x[1] / float(x[0]), reverse=True)for i in range(len(matrix)):# 如果当前物品的重量小于等于背包剩余容量if matrix[i][0] < max:# 将该物品的价值加到总价值中re += matrix[i][1]# 减少背包的剩余容量max -= matrix[i][0]# 标记该物品为已选中re_list[i] = 1else:# 如果物品重量大于背包剩余容量，只能选取部分物品# 计算能够选取的最大价值，并加到总价值中re += max * matrix[i][1] / float(matrix[i][0])# 标记选取了部分物品re_list[i] = max / float(matrix[i][0])break# 返回排序后的matrix，每个物品的选取状态列表re_list，以及总价值rereturn matrix, re_list, re