Milad's blog

Coin Problems with list of values have to be made
By Milad, history, 4 years ago, In English

Hi,

I got stuck in this problem and I will welcome your solutions.

We have $$$N$$$ coins with different values $$$v_1$$$,$$$v_2$$$,...,$$$v_N$$$. We want to find out whether it is possible to put them into $$$M$$$ groups in which:

1- Every coin has to be assigned to exactly one group.

2- The sum of coin values in each group has to be at most $$$K$$$.

Is this problem have any solution better than checking all assignments?

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by Milad (previous revision, new revision, compare).

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

Shouldn't greedy work here?
We can go through coins from the most expensive one to the cheapest one, and additionally for every group, we store how much money we can add to this group in multiset (initially we have a set of $$$m$$$ $$$k$$$-s). Every time we just place a coin in a group, that has the most free space. If there are no such groups, then the answer is -1.

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

    Consider this test: K=9, M=2, v=[5,4,4,3,2]

    This greedy produces [9,9]->[4,9]->[4,5]->[4,1]->[1,1]->no room for 2, but it's possible [5+4,4+3+2]

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

What're the constraints on $$$N,M,K$$$ and $$$v_i$$$? Also what's the source of the problem?

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

    Just a random question in my mind.

    I would like to overthink on my own problems.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

This problem is NP-Complete [edit].

"The decision problem (deciding if items will fit into a specified number of bins) is NP-complete.[2]" https://en.wikipedia.org/wiki/Bin_packing_problem

→ Reply