Knapsack problem/Bounded: Difference between revisions
Content added Content deleted
(Added Wren) |
|||
| Line 851: | Line 851: | ||
return nil if taken.total_value + 1.0 * candidate.value / candidate.weight * remaining_weight < @threshold_value |
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) |
# now recursively check all variants (from taking maximum count to taking nothing) |
||
max_count = {candidate.count, remaining_weight / candidate.weight}.min |
max_count = {candidate.count, remaining_weight // candidate.weight}.min |
||
(0..max_count).reverse_each do |n| |
(0..max_count).reverse_each do |n| |
||
mask = taken.mask.clone |
mask = taken.mask.clone |
||