A snack machine is broken; here is how it behaves: A person tries to buy a snack. If no bags of that snack are left, the machine does nothing. If any bags of that snack are left, the machine charges the person for his chosen snack. the machine then gives the person a DIFFERENT snack (possibly none if the machine is out of the different snack!)

Although the machine is broken, it is at least consistent. Whenever a customer buys a snack from position i, the machine vends from position f(i), where f is some predictable function. We want to buy snacks from the machine and then sell the snack delivered by the machine for its market price (which may be different from the price the machine charges. If a cheap snack is at position i and a valuable snack is at f(i) we can make a profit.

Assuming we can always find buyers who will pay the market price and that we have plenty of money for buying snacks, what is the maximum profit we can achieve if we make wise choices?

For each position i in the machine we are given: f(i) The position that the machines dispenses if we pay for item i price The price the machine charges us for selectint i marketprice The price we can get for selling item i quantity of item i available in the machine.

Example: 3 2 2 3 8 3 1 5 6 1 9 4 7 This machine has 3 types of item. 8 bags of item 1, 6 of item 2, 7 of item 3. If we pay $2 for item 1 we will get item 2 which we could sell for $5. By making wise choices we can make a profit of $39. First get all of item 3 by choosing item 2 7 times. Then choose item 1 6 times. Sell those 13 items for 7*$4 + 6*$55 = $58. We have spent 7*$1+6*$2 = $19. So the profit is $39 which is the best we can do.

Example 3 1 2 3 1 2 3 4 1 3 4 5 1 best profit is $3

5 5 9 2 2 1 1 7 4 2 3 6 3 2 2 9 6 1 4 5 1 best profit is $22

Algorithm? Analysis, defining n to be the number of types of item in the machine.