Noluck_167's blog

Help Needed in a question
By Noluck_167, history, 11 months ago, In English

Can someone please help me out with the solution of this problem "Natsya decided to visit a local store, which has n items. The i-th item has price a[i]

She has to buy k items out of the n items such that total price of all the items bought is minimum.

In how ways she can buy k items such that the overall price is minimum?"

1<=k<=n<=50 a[i]<=n

I have tried to solve it but it is failing in some hidden cases Code.

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is just number of subsequence with K elements with minimum sum. You can do this with dp.

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

    How Dp ? Its greedy

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

      right, my bad, i misread the statement that we can select any number of elements with sum K. But since number of elements selected is K its just simple combinations

      → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Using maps, maximum value elements that belongs to K chosen

ways = totalFreq C usedFreq C = combinations NCR = n!/r!*(n-r)! try using mod (1e9+7) if exceeding limitconstraint

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first find out the frequency of each element in the store and store it in a map. also find the minimum cost. now you need to use simple permutation and combinations. suppose you had 4 items with price 2 and you are only buying 2 items , then you can doit in 4c2 ways

→ Reply