自定义实现分数背包问题Greedy algorithm的技术问询

核心思路拆解 #

你提到的贪心策略完全契合分数背包的最优解法——优先选择单位重量收益最高的物品，具体逻辑可以拆解为更清晰的步骤：

• 预先为每个物品计算单位重量收益（profit/weight），将结果存入profitPerWeight数组
• 在背包还有剩余容量时，循环筛选当前单位收益最高的物品
• 通过getFraction()函数计算该物品能放入背包的最大比例：如果物品总重量小于剩余容量就全放，否则只放剩余容量对应的比例
• 累加对应收益，更新剩余背包容量，直到背包被完全填满

代码实现示例 #

下面是基于你思路的Python代码参考，注释里补充了关键细节：

def getFraction(item_weight, remaining_capacity):
    # 计算可放入的物品比例，同时返回实际占用的背包重量
    if item_weight <= remaining_capacity:
        return 1.0, item_weight  # 物品能全放，比例为1
    else:
        return remaining_capacity / item_weight, remaining_capacity  # 只能放部分，按剩余容量算比例

def knapSack(capacity, weights, profits):
    n = len(weights)
    # 初始化单位重量收益数组
    profitPerWeight = [profits[i]/weights[i] for i in range(n)]
    total_profit = 0.0
    remaining_cap = capacity

    # 循环填充背包直到无剩余容量
    while remaining_cap > 0:
        # 找到当前单位收益最高的物品索引
        max_pw_index = profitPerWeight.index(max(profitPerWeight))
        current_weight = weights[max_pw_index]
        current_profit = profits[max_pw_index]
        
        # 计算可放入的比例和实际重量
        fraction, used_weight = getFraction(current_weight, remaining_cap)
        # 累加收益
        total_profit += current_profit * fraction
        # 更新剩余容量
        remaining_cap -= used_weight
        # 标记该物品已处理，避免重复选择
        profitPerWeight[max_pw_index] = -1

    return round(total_profit, 2)

# 测试用例
if __name__ == "__main__":
    capacity = 50
    weights = [10, 20, 30]
    profits = [60, 100, 120]
    print(f"背包最大收益为: {knapSack(capacity, weights, profits)}")

优化提示 #

• 上面的实现每次用max()找最高收益物品的时间复杂度是O(n)，如果物品数量较多，建议先对物品按单位收益降序排序，之后只需遍历一次就能完成填充，时间复杂度可从O(n²)优化到O(n log n)
• 浮点数计算可能存在精度误差，最后可以用round()保留2-3位小数保证结果可读性

内容的提问来源于stack exchange，提问作者Cantaff0rd