Similar to the idea mentioned in the tutorial, the primal problem to fill m cups evenly using n bottles, where each bottle contains w units, and each bottle is to be poured in at most 2 different cups, is equivalent to the equivalent dual problem when each bottle contains exactly m units, and all the poured amounts are integer numbers. In the dual problem, the capacity of each cup is exactly n units. The amounts of the primal problem are then simply computed as the amounts computed in the dual problem times the scale factor w/m.

In test 1 [ n=2, w=500, m=3 ], the scale factor is 166.666667, and the given solution is equivalent to the following solution of the dual problem.

1 2

2 2

2 1 1 1

In test 2 [ n=4, w=100, m=5 ], the scale factor is 20, and the given solution is equivalent to the following solution of the dual problem.

3 1 4 3

1 4

4 2 2 2

3 4

2 3 1 1

In test 3 [ n=4, w=100, m=7 ], it is impossible in the dual problem to pour any bottle in one cup only, since the bottle size m is larger than the cup capacity n. All the 2-cups integer partitions 1+6, 2+5, and 3+4 of one bottle are also impossible. In the first two partitions, the second part is larger than the cup capacity. In the third partition, pouring the first part in some cup would leave a 1-unit space in such cup. This space cannot be filled from another bottle, as it would leave 6 units in such bottle that cannot be poured in one cup only.

In test 4 [ n=5, w=500, m=2 ], the scale factor is 250, and the given solution is equivalent to the following solution of the dual problem.

4 1 5 2 2 2

3 2 1 2 4 1

Finally, it should be noted that the dual problem is equivalent to finding a matrix A with n rows that represent the bottles, m columns that represent the cups, and positive integer elements that represent the amount poured from bottle i in cup j. The following are the constraints that the sought matrix A satisfies:

1. The sum of all elements in each row is exactly m.

2. The sum of all elements in each column is exactly n.

3. Each row contains either one or two non-zero elements only.

Hope that this explanation is sound and helpful enough.

The following is a C++17 implementation of the greedy algorithm based on the integer dual problem. 36085263