Anonymous user
Knapsack problem/Bounded: Difference between revisions
m
→Branch and Bound solution
(Added Wren) |
|||
Line 851:
return nil if taken.total_value + 1.0 * candidate.value / candidate.weight * remaining_weight < @threshold_value
# now recursively check all variants (from taking maximum count to taking nothing)
max_count = {candidate.count, remaining_weight // candidate.weight}.min
(0..max_count).reverse_each do |n|
mask = taken.mask.clone
| |||