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?
Auto comment: topic has been updated by Milad (previous revision, new revision, compare).
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.
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]
What're the constraints on $$$N,M,K$$$ and $$$v_i$$$? Also what's the source of the problem?
Just a random question in my mind.
I would like to overthink on my own problems.
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
My gratitude.