A person is shopping at a store that carries n different food items as packaged goods. A box of the i-th item will bring the shopper a benefit of bi and costs pi dollars, where bi and pi are integers.
The shopper would like to receive maximum benefit, subject to the requirement that they can't spend more than P dollars in total. So, the problem is which boxes to take (they can take multiple boxes of the same item).
This is known as the integral shopping problem. In the fractional shopping problem, the same n items are sold in bulk, so the shopper can take as much or as little as they like of each food item, instead of having to buy a whole box or nothing.
1. Suppose that the items have the same order if we sort them by price from low to high, and if we sort them by benefit from high to low. Give an efficient algorithm to find an optimal solution to the integral shopping problem in this special case, and argue that your algorithm is correct. Hint: Describe the algorithm in English (1 line). Argue correctness in 3 lines.
2. Prove that the fractional version has the following property: the optimal solution can be found by making a series of locally optimal choices. Therefore, give a greedy algorithm to solve this version and proof it correct. Hint: Ditto.
Solve using Dynamic Programming:
1) Write the identity for the OPT value.
2) Explain why the identity holds.
3) Describe data structure you will use to store OPT value for the subproblems and the order in which you will fill out the entries in your data structure.
4) In the problems you are asked to return the solution ( not just the value of the solution), state the additional information you record which will allow you to retrace your steps and report an optimal solution.
5) Bound the running time by the size of the data structure and the work per entry in it.