49 lines
1.8 KiB
Python
49 lines
1.8 KiB
Python
|
"""
|
|||
|
|
给定 n个物品，第 i 个物品的重量为 w[i-1]、价值为 v[i-1]，和一个容量为 cap 的背包。
|
|||
|
|
每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算。
|
|||
|
|
问在限定背包容量下背包中物品的最大价值。
|
|||
|
|
|
|||
|
|
分数背包问题和 0-1 背包问题整体上非常相似，状态包含当前物品 i 和容量 c，目标是求限定背包容量下的最大价值。
|
|||
|
|
不同点在于，本题允许只选择物品的一部分。如图 15-4 所示，我们可以对物品任意地进行切分，并按照重量比例来计算相应价值。
|
|||
|
|
|
|||
|
|
对于物品 i，它在单位重量下的价值为 v[i-1]/w[i-1]，简称单位价值。
|
|||
|
|
假设放入一部分物品 i，重量为 w，则背包增加的价值为 w*v[i-1]/w[i-1]。
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
"""
|
|||
|
|
贪心策略确定：
|
|||
|
|
|
|||
|
|
最大化背包内物品总价值，本质上是最大化单位重量下的物品价值。由此便可推理出图 15-5 所示的贪心策略。
|
|||
|
|
|
|||
|
|
将物品按照单位价值从高到低进行排序。
|
|||
|
|
遍历所有物品，每轮贪心地选择单位价值最高的物品。
|
|||
|
|
若剩余背包容量不足，则使用当前物品的一部分填满背包。
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
class Item:
|
|||
|
|
def __init__(self, w: int, v: int):
|
|||
|
|
self.w = w # 物品重量
|
|||
|
|
self.v = v # 物品价值
|
|||
|
|
self.avg = self.v / self.w
|
|||
|
|
|
|||
|
|
|
|||
|
|
def fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:
|
|||
|
|
items = [Item(w, v) for w, v in zip(wgt, val)]
|
|||
|
|
items.sort(key=lambda item: item.avg, reverse=True)
|
|||
|
|
|
|||
|
|
res = 0
|
|||
|
|
for item in items:
|
|||
|
|
if item.w <= cap:
|
|||
|
|
# 若剩余空间充足，则将当前物品整个拿走
|
|||
|
|
res += item.v
|
|||
|
|
cap -= item.w
|
|||
|
|
else:
|
|||
|
|
# 若剩余空间不足，则拿走当前物品的部分
|
|||
|
|
res += (item.avg) * cap
|
|||
|
|
break
|
|||
|
|
|
|||
|
|
return res
|
|||
|
|
|
|||
|
|
|