You go into a store and want to buy several items. The store has n different items. Item i is priced at $pi, and you have a value of $vi for this item. You want to purchase a set S of items so as to maximize your net utility from the purchasethe total value you get minus the price you pay. In order to do so, you should buy precisely the items for which vi > pi. However, there is a catch. If you spend a total of at least T dollars, you get a 10% discount on your total payment. So it may make sense to buy some items for which vi pi.

For example suppose that the store has three items, each of which you value at $10. Suppose that the three items are priced at $9, $11, and $13 respectively, and the discount threshold T is $15. Then, without the discount you would want to buy only the first item, which brings you a net utility of $1. However, with the discount, it makes sense to buy the first two items. This brings you a total value of $20 at a price of 90% $20, or a net utility of $2.

In the decision version of this problem, you are given the n positive integral prices, n positive integral values, the discount threshold T, and a utility target U. Your goal is to determine whether there is a set S of items that brings you utility at least U. You will prove that this problem is NP-hard by providing a mapping reduction.

(a) Specify which problem you will reduce to what. (b) Describe your mapping reduction.

(c) Prove that the mapping reduction is correct. (Remember that you need to show two implications.)