Distribute i no. of items in n no. of boxes, where each box has different capacity level c1, c2

Question

I have to distribute i. no. of items into n no. of boxes where each box has different capacity level c1, c2 ... cn. I want to distribute the items in ratio of their capacity. So the box with highest capacity will contain highest no. of items and vice versa. The capacities may not be in ascending order. The capacities can also be 0. Also, if the no. of items exceed the total capacity, then fill all the boxes upto their maximum capacity.

Is there already a solution for this problem?

Because I've written following algo. But it's not efficient. Also its looping infinitely at following input. Since the -2 difference is never settled. So there must also be other use cases where it breaks.

int[] arrCap = {1,1,0,1,1};
new Distributor(arrCap, 2).distribute();



import java.util.Arrays;
public class Distributor {

    /** Capacity of each box */
    private final int[] boxCapacity;
    /** Total no. of boxes */
    private final int NO_OF_BOXES;
    /** Total no. of items that are to be distributed into each box  */
    private final int NO_OF_ITEMS;
    /** Total capacity available. */
    private long totalCapacity;
    /** Fractionally ratio distributed items according to capacity */
    private float[] fractionalRatios;
    /** Ratio distributed items according to capacity */
    private int[] ratioDistributedCapacity;
    /** Sorted Rank of distributed items in ascending / descending order */
    private int[] rankIndex;
    /** The difference between the totalCapacity and total of ratioDistributedCapacity */
    private int difference;

    /**
     * Validates the total capacity and no. of items to be distributed.
     * Initializes the distributor with box capacity array, no of items.
     * Implicitly calculates no. of boxes as length of box capacity array.
     * @param boxCapacity Array of capacity of each box.
     * @param noOfItems No. of Items to be distributed.
     */
    public Distributor(int[] boxCapacity, int noOfItems) {
        calculateBoxes(boxCapacity);
        this.boxCapacity = boxCapacity;
        this.NO_OF_ITEMS = noOfItems;
        NO_OF_BOXES = boxCapacity.length;
        ratioDistributedCapacity = new int[NO_OF_BOXES];
        rankIndex = new int[NO_OF_BOXES];
    }

    /**
     * Calculates the ratio into which the items are to be distributed.
     * Actually assigns the items into each box according to the ratio.
     * @return Array of int[] containing ratio distributed items according to its capacity.
     */
    public int[] distribute() {
        // If NO_OF_ITEMS to be distributed is more than totalCapacity then distribute all the items upto full capacity
        if (NO_OF_ITEMS >= totalCapacity) {
            ratioDistributedCapacity = boxCapacity;
        } else {
            calculateRatioAndDistribute();
        }
        return ratioDistributedCapacity;
    }

    /**
     * Calculates the ratio & distributes the items according to the capacity.
     */
    private void calculateRatioAndDistribute() {
        fractionalRatios = new float[NO_OF_BOXES];
        for (int i=0; i<NO_OF_BOXES; i++) {
            fractionalRatios[i] = ((float) boxCapacity[i] * (float) NO_OF_ITEMS) / (float) totalCapacity;
            ratioDistributedCapacity[i] = Math.round(fractionalRatios[i]);
        }
        print(fractionalRatios);
        print(ratioDistributedCapacity);
        // keep redistributing the difference until its not 0
        while ((difference = rectifyAndGetDistributionResult()) != 0) {
            redistribute();
        }
        print(ratioDistributedCapacity);
    }

    /**
     * Redistributes the difference between the already allotted ratioDistributedCapacity array.
     * Also if the difference is 0 that means everything is already settled.
     * No more further need to do anything.
     * @param difference the difference that needs to be settled to equal the no. of items with total distributed items.
     */
    private void redistribute() {
        if (difference > 0) {
            // calculate distribution ranks in ascending order
            calculateDistributionRanks(true);   // orderDescending = true
            // eliminate the invalid ranks from rankIndex
            eliminateInvalidRanks();
            // In case all the ranks have become invalid. In this case the rankIndex will be empty.
            // So we need to re calculate the distribution ranks in opposite order.
            if (rankIndex.length == 0) {
                calculateDistributionRanks(false);  // orderDescending = false
            }
        } else if (difference < 0) {
            // calculate distribution ranks in descending order
            calculateDistributionRanks(false);  // orderDescending = false
            // eliminate the invalid ranks from rankIndex
            eliminateInvalidRanks();
            // In case all the ranks have become invalid. In this case the rankIndex will be empty.
            // So we need to re calculate the distribution ranks in opposite order.
            if (rankIndex.length == 0) {
                calculateDistributionRanks(true);   // orderDescending = true
            }
        }
        // add / substract 1 from the ratioDistributedCapacity of the element in order of the rankIndex
        // according to negative / positive difference until the difference becomes 0.
        final int len = rankIndex.length;
        for (int i=0; i<len; i++) {
            if (difference == 0) {
                break;
            } else if (difference > 0) {
                ratioDistributedCapacity[ rankIndex[i] ]++;
                difference--;
            } else if (difference < 0) {
                ratioDistributedCapacity[ rankIndex[i] ]--;
                difference++;
            }
        }
    }

    /**
     * If the value of any ratioDistributedCapacity element exceeds its capacity or is less than 0,
     * revert it with its initial capacity value.
     */
    private void rectify() {
        for (int i=0; i<NO_OF_BOXES; i++) {
            ratioDistributedCapacity[i] = ((ratioDistributedCapacity[i] > boxCapacity[i]) || (ratioDistributedCapacity[i] < 0)) ? boxCapacity[i] : ratioDistributedCapacity[i];
        }
    }

    /**
     * Calculates the distribution ranks i.e. indexes of fractionalRatios array.
     * Sorts them into ascending or descending order.
     * @param orderDesc Sort order. true for descending and false for ascending.
     */
    private void calculateDistributionRanks(boolean orderDesc) {
        // Copy fractionalRatios array to another tmp array. Note:- Use fractionalRatios so ranking can be more accurate.
        float[] tmp = Arrays.copyOf(fractionalRatios, NO_OF_BOXES);
        // Sort the array in ascending order
        Arrays.sort(tmp);
        // re-initialize the rankIndex array
        rankIndex = new int[NO_OF_BOXES];
        for (int i=0; i<NO_OF_BOXES; i++) {
            innerLoop: for (int j=0; j<NO_OF_BOXES; j++) {
                if (tmp[i] == fractionalRatios[j]) {
                    // Store the array index of unsorted array if its value matches value of sorted array.
                    rankIndex[i] = j;
                    break innerLoop;
                }
            }
        }
        // reverse the rank array if orderDesc flag is true
        if (orderDesc) reverse();
        print(rankIndex);
    }

    /**
     * Remove the indexes from rank which are already full or equal to 0
     * or are not eligible for increment / decrement operation.
     */
    private void eliminateInvalidRanks() {
        final int len = rankIndex.length;
        int invalidRankCount = 0;
        final int markInvalidRank = -1;
        for (int i = 0; i < len; i++) {
            if (boxCapacity[rankIndex[i]] <= 0) {
                // mark this rank number as invalid, for removal
                rankIndex[i] = markInvalidRank;
                invalidRankCount++;
                continue;
            }
            if (difference > 0) {
                if ((ratioDistributedCapacity[rankIndex[i]] >= boxCapacity[rankIndex[i]])) {
                    // mark this rank number as invalid, for removal
                    rankIndex[i] = markInvalidRank;
                    invalidRankCount++;
                    continue;
                }
            } else if (difference < 0) {
                if (ratioDistributedCapacity[rankIndex[i]] <= 0) {
                    // mark this rank number as invalid, for removal
                    rankIndex[i] = markInvalidRank;
                    invalidRankCount++;
                    continue;
                }
            }
        }
        int[] tmp = new int[(len - invalidRankCount)];
        int j = 0;
        for (int i = 0; i < len; i++) {
            if (rankIndex[i] != markInvalidRank) {
                tmp[j++] = rankIndex[i];
            }
        }
        rankIndex = tmp;
        print(rankIndex);
    }

    /**
     * Rectifies the elements value inside ratioDistributedCapacity.
     * Calculates the total of already distributed items.
     * @return Difference between total distributed items and initial no. of items that were to be distributed.
     */
    private int rectifyAndGetDistributionResult() {
        rectify();
        int remaining = NO_OF_ITEMS;
        for (int tmp: ratioDistributedCapacity) {
            remaining -= tmp;
        }
        return remaining;
    }

    /**
     * Validates the capacity array and no. of items to be distributed.
     * @param arrCapacity Array of capacity of each box.
     */
    private void calculateBoxes(int[] arrCapacity) {
        for (int i: arrCapacity) {
            totalCapacity += i;
        }
    }

    /**
     * Prints the array elements and the total of the elements within it.
     * @param x
     */
    private void print(int[] x) {
        final int len = x.length;
        final StringBuilder sb = new StringBuilder("");
        for (int i=0; i<len; i++) {
            sb.append(x[i]).append(", ");
        }
        System.out.println(sb.toString());
    }

    /**
     * Prints the array elements and the total of the elements within it.
     * @param x
     */
    private void print(float[] x) {
        final int len = x.length;
        final StringBuilder sb = new StringBuilder("");
        for (int i=0; i<len; i++) {
            sb.append(x[i]).append(", ");
        }
        System.out.println(sb.toString());
    }

    private void reverse() {
        final int len = rankIndex.length;
        for (int i=0; i < (len/2); i++) {
            rankIndex[i] += rankIndex[len - 1 - i]; //  a = a+b
            rankIndex[len - 1 - i] = rankIndex[i] - rankIndex[len - 1 - i]; //  b = a-b
            rankIndex[i] -= rankIndex[len - 1 - i]; //  a = a-b
        }
    }
}

Answer 1

Two approaches come to mind

1. Optimal Rounding

   Treat the problem like an optimal rounding problem. Since you want the items distributed in the boxes "in ratio of their capacity", then for each box compute their share which is "capacity / sum of all capacities". Then multiply that share by the number of items. That'll usually give you a fractional number of items for each box. I assume your items are indivisible. Now you just have to determine how to "optimally round" these values. Here is one SO question that discusses how to do that. You can also search for "optimal rounding under integer constraints" to find several papers on the subject.

2. Fair Division

   Treat the problem using fair division. The link covers numerous approaches (most are approximations). However, the key part will be how will each of your boxes ascribe a value to each item, so that the algorithms will know how to parcels the items. You can use a metric that is proportional to their capacity.

Answer 2

I wonder if you do simple math to find out ratio would solve the problem easily. So Ni is number of items you have to distribute, B sum of all boxes capacity(ie c1+c2+...+cn)

So R = Ni/B would be your ration. R*cn would be number of items you would want to put into box n

Example: you have total of 8 items. and 2 boxes capacity 4, 12(N1 = 16). R = 8/(4+12) = 1/2 for box would have R*4 = 2 second box would have R*12 = 6

Of course you would have to handle rounding issues, there will be +/-1 items in the boxes.

PS For fixing rounding issue you will do following. you create a variable sumSoFar = 0 //initial value

box1 contains R*c1 then you add sumSoFar+=Math.round(R*c1)

box2 contains Math.round(R*c2) then you add sumSoFar+=Math.round(R*c2)

for last box you put N1-sumSoFar So you distribute all values.

here is the code:

static int[] distribute(int[] boxes, int items) {
    int[] result = new int[boxes.length];
    int sumSoFar = 0;
    int totalCapacity = 0;
    for (int box : boxes) {
        totalCapacity += box;
    }
    float R = (float) items / totalCapacity;

    for (int i = 0; i < boxes.length - 1; i++) {
        int box = boxes[i];
        result[i] = Math.round(R * box);
        sumSoFar += result[i];
    }
    result[boxes.length - 1] = items - sumSoFar;
    return result;
}

Calling:

System.out.println(Arrays.toString(distribute(new int[]{1, 2}, 10)));
System.out.println(Arrays.toString(distribute(new int[]{4, 12}, 8)));

Results:

[3, 7]
[2, 6]