student's blog

By student, history, 6 weeks ago, In English

Distribution — exhausting credits with a small overflow in each group Write a python program

Problem: Write a Python program to distribute amounts to exhaust all the credits. The distribution should factor such that sum of amounts is higher than the credit. It shouldn’t be equal to or less than the credit. A group can have multiple credits and multiple amounts can be combined. However, the group cannot have more than N items (the example below is 4, but in real life it can be thousand). Once a group reaches N items, then start a second group. Or you can have one credit per group and the rest amounts. All amounts need to be consumed. There will be situations where there is no solution, and program will do the best it can to distribute.

The problem is a variation of the bin packing problem. While the bin packing problem optimizes to fit the bin, we need to optimize to overflow just enough to fill all the bins with a bit of overflow.

Let’s walk through an example to understand the complexity. We have four credits, 12 amounts, and our batch size can’t exceed four.

Credits : [350, 350, 100, 50]

Amounts : [250, 200, 150, 85, 80, 60, 20, 15, 10, 5]

The sum of credits is 850, and the sum of invoices is 875, which will result in a payment of 25.

As our group size is four, we could fill the first bin with [250, 200, 150] amounts and a credit of [350]. However, the other three bins would have a credit left. It is also not optimal because we didn’t exhaust all the credit.

We could arrange the bins [350][200, 150, 5], [350][250, 85, 20], [100][80, 15, 10], and [50][60]. With each bin, we need the minimalist overflow possible.

With the same credits example, let’s slightly change one of the values of the amounts from 60 to 50. While the sum of credits is the same, the sum of invoices is 865 now, a difference of 15. Considering there are four bins and the lowest amount is 5, it is doubtful we will have a solution without resulting a group to have equal credit and amount. The best optimization in this scenario is still the same with one difference – the last bin having [50], resulting a 0 difference.

Typically, in a combined list of 100000, the number of credits will be fewer (less than 50) but the number of amounts can be in tens of thousands. When the program distribute the group size can’t be more than 1000.

  • Vote: I like it
  • 0
  • Vote: I do not like it