Hey fellow nerds, I have a math question :)

I need to split a pile of coins (1s, 2s, 5s, 10s and so on) into a number of piles, let's say four, so that each pile has the same amount of money, but not necessarily the same amount of coins. Does anybody know of such an algorithm?

spontaneously, i'd say:

- split most significant coins into n piles (with n=4 in this case)
- if count(most significant coins) is no multiple of n, fill piles with smaller values with combinations of less significant coins, preferring those with higher values (with criterion that pile has at least value of other piles, it might be bigger)
- repeat these 2 steps with remaining coins until they are used up
- if per each round, piles can not be set with the same values, balancing of these values is tried in the next round

not sure if this works or is understandable, i just woke up ._.

That's the knapsack problem: https://en.wikipedia.org/wiki/...

@Fast-Nop lol we're doing this for AI classes

i think you'd have to settle for an approximation, getting the best solution is just consuming

@soull00t thank you for that. Sounds like a good approximation.

@Fast-Nop that is exactly what I was looking for

Thank you both! :)

I'm not sure if this is *exactly* the knapsack problem, as it might be that slightly above the target split value is acceptable and better than being more short of the value, not sure if it is acceptable to leave coins unallocated to any pile, etc, but I think you'd do pretty well with:

Set the target value to be the total value of the coins, divided by four, rounded up to the next higher integer value. For each pile, put in the largest of the available unallocated coins until no more coins can be added without exceeding the target value. Go to the next pile when no further unallocated coins can be added. Stop when all piles have been created, as do not want to loop forever.

It's entirely possible that there is no place to allocate a coin, e.g. with 10p, 1p, 1p, 1p , if the constraint is to never exceed the target amount.

@spongegeoff That would probably work quite nicely! The next issue that I didn't mention is that I'd also like to secondarily even out the weights as well, if that's even possible. Because in my case I might be handing out hundreds of euros in cash 😅