I am trying to solve an algorithmic problem that is described as follows:
There are K types of items and 2 supermarkets. Each selling all K types of items but at different prices. Please find the maximum number of unique items that can be bought given that we can spend only X dollars in supermarket 1 and Y dollars in supermarket 2.
Bounds:
1 <= K <= 2000
1 <= X, Y <= 10000Example:
K = 5, X = 6, Y = 12
Supermarket 1 (We have 6 dollars):
Type 1: 5
Type 2: 1
Type 3: 5
Type 4: 6
Type 5: 3Supermarket 2 (We have 12 dollars):
Type 1: 3
Type 2: 5
Type 3: 4
Type 4: 6
Type 5: 7In this case, the optimal answer would be 4 because we can buy item types 1 and 2 in supermarket 1, item types 3 and 4 in supermarket 2.
Problem source: here
I have interpreted it as a coin change problem where one must collect the maximum number of different denominations. Hence, I don't think that a greedy algorithm can work here (since it fails for coin change). More precisely, if one sorts the 2 item lists according to item-price pairs, it would clearly fail since one type of item may be very expensive in both lists.
The next method of my list is to use DP. But, I think DP might be too slow.
Could anyone please advise me on a better solution to solve this problem?
Edit:
I managed to solve the problem thanks to data_h and Deemo's help in the comments. The complete solution can be found here
Once again, thanks a lot for all your help!