Lance_HAOH's blog

Buy maximum number of unique items given limited budget
By Lance_HAOH, history, 8 years ago, In English

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 <= 10000

Example:

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: 3

Supermarket 2 (We have 12 dollars):

Type 1: 3
Type 2: 5
Type 3: 4
Type 4: 6
Type 5: 7

In 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!

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Share the link to the problem, please.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Done. I just added a link to the problem source.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Try sorting the items by their price in the first supermarket. Now if you buy item I in the first supermarket, you should buy all the other items with index less than I. (This is just a hint, not the whole solution)

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        That will get me the maximum number of unique items for the first supermarket. If I perform the same operation on the second supermarket, I will also get the maximum number of unique items from there as well. But summing the maximum number of unique items from both supermarket may not give me the greatest total number of unique items. How could I handle this?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Assume the last item you're going to buy from the first supermarket is the i-th one. You have to buy all the items from 0 to I(otherwise, we can find a better solution). Since the i-th item is the last item you're buying from the first supermarket, you want to minimize the total money you're spending in the second supermarket during the process(so you can buy as many items as possible amongst the items from I+1 to n). You can use dynamic programming to calculate the minimum money you have to spend in the second supermarket to buy the first i items. Then, you can use dynamic programming to calculate the maximum number of items amongst the items from I+1 to n that you can buy from the second supermarket using the remaining money.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            If I understood correctly, we need to sort both lists in ascending order of price and then we perform the following:

            ///for i from 1 to k
   ///for each j from 1 to k
     ////If supermarket 2's item is cheaper take it.
     ////Else
         /////Take item from supermarket 1
         /////Now perform DP on supermarket 2's list starting from i+1 to get the maximum number of unique items
         /////exit loop
   ///Save global max

            The complexity of the algorithm is O(K^2).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              I think that the DP's complexity is O(KX), which is something like f[i][j] denotes the minimum cost for supermarket 2 if we buy the first i's items(in market 1's order) and spend j dollars in supermarket 1.

              For the remaining items, by using greedy method, you may solver it in total O(KX) complexity.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Actually, I don't quite understand what you mean by minimizing the cost for supermarket 2 for the first i items.

                From what I understand, supermarket 2's list is unsorted.

                Now, let's say we take the first i items from supermarket 1. Then why would we have to spend money in supermarket 2 to buy those i items again?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  Assume the last items you buy in supermarket 1 is i, you have to buy all the items from 0 to i. which don't means that you have to buy all of these in supermarket 1. (Perhaps you can get some of these free in market 2 :P)

                  After we got the first i items, the most important things we really care about is that how much dollars still remaining for supermarket 2.

                  Using the dp method I said before, you know exactly how much I cost in supermarket 1 and 2 for the first i's items. Erase all the items you have bought (The first i's items in market 1's order.) and sort the remaining items in market 2's order, you may buy these using greedy method.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Thank you so much for your patience and detailed explanation! I tried my hands at the implementation. Unfortunately it only passes 15% of the test cases. I constructed various test cases and the algorithm passed all of them. I am positive that the DP is correct as I printed the DP matrix and manually checked the values.

                  My implementation here

                  Would you be willing to take a quick look and give me some suggestions why my code is faulty? I have added a lot of comments so that it is easy to understand.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  First, swap your dimensions of dp(some thing like dp[2000][10000])

                  Second, If mon < 0, you may break directly, I'm not very clear about how the from1 works.

                  → Reply