背包算法中的 min{wi, W − w} 函数

Question

Algorithm FractionalKnapsack(S, W ):
Input: Set S of items, such that each item i ∈ S has a positive benefit bi and a
positive weight wi; positive maximum total weight W
Output: Amount xi of each item i ∈ S that maximizes the total benefit while
not exceeding the maximum total weight W
for each item i ∈ S do 
 xi ← 0
 vi ← bi/wi // value index of item i 
w ← 0 // total weight
while w < W and S ̸= ∅ do
 remove from S an item i with highest value index
 a ← min{wi, W − w} // more than W − w causes a weight overflow 
 xi ← a
 w←w+a

我正在尝试在 Ruby 中实现上面的伪代码，我已经成功实现了一个优先级队列，但我只需要有人为我解释这一行：

a ← min{wi, W − w} // more than W − w causes a weight overflow

min 函数究竟应该做什么？以及应该如何实施？

Answer 1

行 a ← min{wi, W − w} 实际上给 'a' 一个值，它是 w[i] 和 W-w 的最小值。

if w[i] < W-w then a ← w[i]
otherwise a ← W-w

对于实施你可以做

[w[i], W-w].min