You have N dollars and you have a list of k items L1, ..., Lk that you wish to purchase from an online store. If you purchase an item, then the online store gives you some reward points. For an item Li , 1<= i <= k, the price and reward values are Pi and Ri, respectively. Both Pi and Ri are integers. Unfortunately, there is a threshold T on the total reward you can earn. In other words, if the sum of reward values for the items you purchase is more than T, then any reward point beyond T will be wasted. Write an efficient algorithm (to the best of your knowledge) to find a list of items within N dollars such that purchasing them will maximize the sum of reward values but will keep the sum within the threshold T (Note: the sum can be equal to T). Briefly describe why it is a correct algorithm, provide pseudocode, and analyze the time complexity. Example: Input: N = 10, k = 3, T = 100, P = [4,6,5], R = [40,70,50] Output: L1, L3. Here is an explanation. Note that you have the following choices: {L1} where price 4 and reward 40. {L2} where price 6 and reward 70. {L3} where price 5 and reward 50. {L1,L2} where price 10 and reward sum 110 (exceeding T). {L1,L3} where price 9 and reward 90. {L2,L3} where price 11 (exceeding N) and reward 120 (exceeding T). Thus the best option that maximizes the reward sum is L1, L3.
You have N dollars and you have a list of k items L1, ..., Lk that you wish to purchase from an online store. If you purchase an item, then the online store gives you some reward points. For an item Li , 1<= i <= k, the price and reward values are Pi and Ri, respectively. Both Pi and Ri are integers. Unfortunately, there is a threshold T on the total reward you can earn. In other words, if the sum of reward values for the items you purchase is more than T, then any reward point beyond T will be wasted. Write an efficient
Example: Input: N = 10, k = 3, T = 100, P = [4,6,5], R = [40,70,50]
Output: L1, L3.
Here is an explanation. Note that you have the following choices:
{L1} where price 4 and reward 40. {L2} where price 6 and reward 70. {L3} where price 5 and reward 50. {L1,L2} where price 10 and reward sum 110 (exceeding T). {L1,L3} where price 9 and reward 90. {L2,L3} where price 11 (exceeding N) and reward 120 (exceeding T).
Thus the best option that maximizes the reward sum is L1, L3.
Step by step
Solved in 2 steps with 3 images
