市桥做网站的公司,高档女装品牌前十名,帝国cms做淘宝客网站,在线免费作图软件本节学习解决部分背包问题,部分背包代表物品可以按照一定比例被分割,而后放入背包内.这是十分经典的用贪心算法解决的问题. 问题描述:
给定一些物品,用matrix表示各个物品的属性,第一项表示物品的质量,第二项表示物品的总价值.现有一背包最大承重为M,试求如何让背包中所装物品…本节学习解决部分背包问题,部分背包代表物品可以按照一定比例被分割,而后放入背包内.这是十分经典的用贪心算法解决的问题. 问题描述:
给定一些物品,用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(keylambda x: x[1] / float(x[0]), reverseTrue)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
