My Blue Heaven is a movie about a mobster who turns to an informant, Vinny. He ends up in witness protection and the Feds send him to a small town no one has ever heard of, in the middle of Arizona. Very far away from his stomping ground of New York, and no wise guys to look out for after ratting out mob bosses. Vinny notices that more and more of his crew find their way to the same small town, where the naive natives are not used to the slick ways of former mobsters.

There is a scene where Vinny and his gang, tired of being goodie-two-shoes in the witness protection program, want to perform a heist just like the old days. They end up ripping off a truck and when they pull up the cargo doors to see what they scored, they are disappointed to find that there are no tvs, no stereos, no large cuts of meat, instead what they are left with is a full trailer of empty Culligan bottles.

"What the hell are we supposed to do with these?" an old gangster asks

Vinny looks at them and sees an opportunity.

"You see the difference between you and me, I don't see a problem here, I see an opportunity."

If the truck hijacked were a collection of wholesale retail items headed for Sam's Club one would want to load the cargo area with as many items as it could. The truck would have medium size, large size, and skinny boxes arranged in such a manner to delivery the maximum payload to its destination, without exceeding the weight capacity of the truck.

However with the small weight of the empty Culligan bottle, the efficiency of the load would be instead of worrying about weight, the load would have be arranged in such a manner to maximize number of bottles into the load without exceeding the volume of the cargo area.

This problem we have with our truck load can be categorized as a knapsack problem. Basically what the knapsack problem is, is pretend you are a burglar and you have a bag. The bag can only hold so much before it will tear. Let's say the max weight the bag can hold is W and you want to maximize the score.

Each item has a weight and a value. For instance let's say that we have 3 items. Item A, B and C. They weigh 5lb,10lb,20lbs respectively, and have a profit of $50,$60,and $140. Let's say that our bag can only hold 30lbs obviously we can't put them all in our bag, so what do we do?

First define the problem so we can approach it recursively

We have w1, w2, w3,...wn items. W as the max weight, and m[i,w] is the max value that can be added with weight less than or equal to w using i items.

• m[0,w] = 0
• m[i,w] = m[i-1,w] if wi > w
• m[i,w] = max(m[i-1,w],m[i-1,w - wi] + vi) if wi less than or equal to w

In our simple example of three items we have W = 30 and now we have to find the entries for each row.

For row 3 we have m[3,30], to find entries in row 2 we have

m[3-1,30] = m[2,30] and m[3-1,30 - w3] = m[2,10]

Now find m[2,30] similarily we have

m[2-1,30] = m[1,30] and m[2-1,30 - w2] = m[1,20]

Find m[2,10] we need m[2-1,10] = m[1,10] and m[2-1,10 - w2] = m[1,0]

Fill out the table ( assuming item 1 does not exceed W )

m[1,0] = $0
m[1,10] = $50
m[1,20] = $50
m[1,30] = $50

Row two apply the formula

m[2,10] = max(m[1,10],$60 + m[1,0] ) if w2 = 10 <= 10
m[1,10] if w2 = 10 > 10
m[2,10] = $60

m[2,30] = max(m[1,30], $60 + m[1,20]) if w2 = 10 <= 30
m[1,30] if w2 = 10 > 30

We get $60 + m[1,20] or $60 + $50 = $110

Finally row 3

m[3,30] = max(m[2,30],$140 + m[2,10]) if w3 = 20 <= 30
m[2,30] if w3 = 20 > 30

Since $140 + $60 > $110 $200 is our max profit.

Vinny: You know, it's dangerous for you to be here in the frozen food section.

Shaldeen : Why is that?

Vinny : Because you could melt all this stuff.