The User Bin Crash puzzle (usrbincrash) is a quick and fun puzzle to solve (note: Facebook took down the original puzzle so I’m linking to another site with the description). After reading the problem statement, it should be easily recognizable as an inverted instance of the knapsack problem. The fact that there is a weight requirement is a dead giveaway. Unlike a burglar trying to maximize the value of the stolen goods in his knapsack, you’re trying to minimize the cost of the goods being thrown out of the plane. Although the knapsack problem is NP-complete, it can be solved in a straightforward manner using dynamic programming.
Of course, it would be no fun to simply reveal the solution. Instead, I’ve decided to formulate the problem in parable form with a tropical theme. Hopefully, it’ll help provide a more intuitive understanding of the knapsack problem. If you’ve been following along with my posts about various Facebook Puzzles and are interested in trying some of them out yourself, getting a good handle on dynamic programming will prove to be quite useful.
Volcano Island
An ancient volcano island tribe holds an annual festival to honor and worship the volcano gods that control the fate of island. It is believed that each year, they need to sacrifice a pound of fruit to the volcano for every fish spotted in the tribal lagoon on the day of last year’s festival. Being an economically and technically advanced people, the island tribe has determined an exact monetary value for each type of fruit. The tribe is also very frugal, and wants to sacrifice just enough fruit to appease the gods but wants to keep its cost down so that it can sell the rest of its fruits to other tribes. After many years of using rough calculations to figure out the amount of fruits to be sacrificed, the tribal council has finally decided to come up with an algorithm to predetermine how much and what types of fruits they should grow to prepare for the coming year.
Given that the tribe needs to sacrifice n pounds of fruits on a given year, with access to a set of different types of fruits, each with a fixed unit weight and value, determine the minimum value that needs to be sacrificed in order to meet the requisite n pounds and appease the gods.
Greedo the Flawed
One of the tribe members, Greedo the Flawed, thinks he has a solution. He takes inventory of the different types of fruits that the tribe can grow, and calculates their weight to cost ratio. The higher the ratio, the more efficient the fruit for sacrifice. For example, suppose a watermelon weighs 5 lbs and costs $3, and a papaya weighs 4 lbs and costs $2; watermelons can add 1.67 lbs for every $1 spent, whereas papayas can add 2 lbs for every $1 spent. Thus, papayas should be considered for sacrifice before watermelons.
| Watermelon | 5 lbs | $3 |
| Papaya | 4 lbs | $2 |
Once the ratios are calculated, Greedo will keep picking the most efficient fruit to be sacrificed until the necessary weight is met. If the total weight exceeds more than is necessary to appease the gods, Greedo will remove the fruit he most recently added, and try to add more of the second most efficient fruit to see if costs can be cut, and so on. Greedo claims that this way, the tribe will be able to sacrifice just enough fruits while keeping the costs to a minimum.
However, the wiser tribal council members immediately see a problem with Greedo’s algorithm. If the gods want 5 lbs of fruit, Greedo’s algorithm would select two papayas for a weight of 8 lbs and a cost of $4; it would not replace a papaya with a watermelon, since that would be more costly. However, sacrificing just one watermelon will meet the required 5 lbs with a cost of just $3. It is apparent that Greedo the Flawed’s algorithm is indeed flawed.
A Better Approach
While the rest of the tribe is debating the merits of Greedo’s approach, an older, much wiser tribal council member steps forward with a solution. Dyno the Pragmatic points out that the key is that when considering a weight n, the optimal cost of including one particular fruit in the solution is simply the optimal cost for “n minus the weight of the fruit” pounds plus the cost of the fruit itself. For example, suppose 10 lbs of fruit are needed, he can take one watermelon and subtract its weight to get 5 lbs. Assuming that he knows what the optimal cost for 5 lbs of fruit is, he simply adds the cost of a watermelon, $3. If he make this calculation for one of every fruit (since he has to add at least one fruit in order to arrive at weight n), and take the result with the minimum cost, then he will get an optimal cost! Dyno proclaims that he can use the ancient art of dynamic programming to build the solution from bottom up and arrive at the optimal solution; he quickly pulls out a stick and starts drawing symbols in the sand.
Let’s see how to implement Dyno’s approach. Suppose that each type of fruit is represented by pairs of the form (weight, cost) and we are given the total weight needed to appease the gods.
def sacrifice(weight, fruits)
# costs[k] = minimum cost for sacrificing k lbs of fruit
costs = Array.new(weight + 1)
costs[0] = 0
for w in 1..weight
# For each weight, pick a fruit that yields us the lowest cost
min = nil
fruits.each do |fruit|
diff = w - fruit[0]
cost = (diff <= 0 ? 0 : costs[diff]) + fruit[1]
min = cost if min.nil? || cost < min
end
costs[w] = min
end
return costs
end
Optimizations
Stepping away from the parable, we can see that this problem is actually a variant of the unbounded knapsack problem. Instead of trying to figure out the maximum value of goods that can fit in a knapsack so that the total weight is less than a given limit, the tribe is trying to figure out the minimum cost of goods that can be thrown out so that the total weight is more than a given limit. The knapsack problem is known to be NP-complete. For a weight W and n fruits, Our dynamic programming solution goes through n fruits W times, for a complexity of O(nW). Alas, the complexity is still not polynomial in the length of the input to the problem. Nevertheless, there are some optimizations we can make to speed up the algorithm, albeit not its complexity.
Since we only care about the cost of the items in the knapsack, the individual item weights only have to remain in proportion to the weight limit. Thus, we can find the greatest common denominator (gcd) of all item weights and the weight limit W, and divide all the weights by this value if it’s greater than one. That will cut down on the size of W, thus reducing the running time. We can easily implement this optimization using Ruby’s gcd function for the Integer class. (Note that you need to call require ‘rubygems’ in order to use the gcd function.) To find the gcd of all the weights, find the gcd of the first pair of values, then find the gcd of that value with the next weight, and so on.
With this optimization in hand, we can implement Dyno’s simple, elegant solution. Here’s what it would look like for an example case of planning for next year’s sacrifice.
#!/usr/bin/ruby
require 'rubygems'
weight = 12
fruits = [[13, 11], [7, 5], [2, 3], [1, 10]]
gcd = weight.gcd(fruits[0][0])
fruits.each { |fruit| gcd = gcd.gcd(fruit[0]) }
if gcd > 1
weight /= gcd
fruits.each { |fruit| fruit[0] /= gcd }
end
result = sacrifice(weight, items)
puts result[weight]
If you enjoyed this post, you should follow me on Twitter @cloudkj. If you’re interested in more puzzle fun, you should check out my posts about various other puzzles, such as Liar Liar, Gattaca, Dance Battle, It’s A Small World, and Refrigerator Madness.
Food For Thought
- How can the program be modified to output the fruits to be chosen, and the units of each fruit?
- How can the algorithm be further optimized by comparing the weight/cost ratios of different fruits?
Comments