部分背包问题

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

问题描述:

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

思路解析:

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

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

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

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

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

完整代码如下:

def bag(matrix, max):
    # 初始化总价值为0
    re = 0
    # 创建一个列表，用于记录每个物品是否被选中，初始化为0
    re_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] = 1
        else:
            # 如果物品重量大于背包剩余容量，只能选取部分物品
            # 计算能够选取的最大价值，并加到总价值中
            re += max * matrix[i][1] / float(matrix[i][0])
            # 标记选取了部分物品
            re_list[i] = max / float(matrix[i][0])
            break
    # 返回排序后的matrix，每个物品的选取状态列表re_list，以及总价值re
    return matrix, re_list, re