Packing item from set of available packs

Question

Suppose there is an Item that a customer is ordering - in this case it turns out they are ordering 176 (totalNeeded) of this Item.

The database has 5 records associated with this item that this item can be stored in:

{5 pack, 8 pack, 10 pack, 25 pack, 50 pack}.

A rough way of packing this would be:

 Sort the array from biggest to smallest.

 While (totalPacked < totalNeeded) // 176
      {
         1. Maintain an <int, int> dictionary which contains Keys of pack id's, 
         and values of how many needed
         
         2. Add the largest pack, which is not larger than the amount remaining to pack, 
         increment totalPacked by the pack size
         
         3. If any remainder is left over after the above, add the smallest pack to reduce 
         waste
               e.g., 4 needed, smallest size is 5, so add one 5; one extra item packed
      }

Based on the above logic, the outcome would be:

You need: 3 x 50 packs, 1 x 25 pack, 1 x 5 pack

Total Items: 180

Excess = 4 items; 180 - 176

The above is not too difficult to code, I have it working locally. However, it is not truly the best way to pack this item. Note: "best" means, smallest amount of excess.

Thus ... we have an 8 pack available, we need 176. 176 / 8 = 22. Send the customer 22 x 8 packs, they will get exactly what they need. Again, this is even simpler than the pseudo-code I wrote ... see if the total needed is evenly divisible by any of the packs in the array - if so, "at the very least" we know that we can fall back on 22 x 8 packs being exact.

In the case that the number is not divisible by an array value, I am attempting to determine possible way that the array values can be combined to reach at least the number we need (176), and then score the different combinations by # of Packs needed total.

How can I tackle this problem?

Answer 1

This is a variant of the Subset Sum Problem (Optimization version)

While the problem is NP-Complete, there is a pretty efficient pseudo-polynomial time Dynamic Programming solution to it, by following the recursive formulas:

D(x,i) = false   x<0
D(0,i) = true
D(x,0) = false   x != 0
D(x,i) = D(x,i-1) OR D(x-arr[i],i

The Dynamic Programming Solution will build up a table, where an element D[x][i]==true iff you can use the first i kinds of packs to establish sum x.
Needless to say that D[x][n] == true iff there is a solution with all available packs that sums to x. (where n is the total number of packs you have).

To get the "closest higher number", you just need to create a table of size W+pack[0]-1 (pack[0] being the smallest available pack, W being the sum you are looking for), and choose the value that yields true which is closest to W.

If you wish to give different values to the different pack types, this becomes Knapsack Problem, which is very similar - but uses values instead a simple true/false.

Getting the actual "items" (packs) chosen after is done by going back the table and retracing your steps. This thread and this thread elaborate how to achieve it with more details.

Answer 2

If this example problem is truly representative of the actual problem you are solving, it is small enough to try every combination with brute force using recursion. For example, I found exactly 6,681 unique packings that are locally maximized, with a total of 205 that have exactly 176 total items. The (unique) solution with minimum number of packs is 6, and that is { 2-8, 1-10, 3-50 }. Total runtime for the algorithm was 8 ms.

public static List<int[]> GeneratePackings(int[] packSizes, int totalNeeded)
{
    var packings = GeneratePackingsInternal(packSizes, 0, new int[packSizes.Length], totalNeeded);
    return packings;
}

private static List<int[]> GeneratePackingsInternal(int[] packSizes, int packSizeIndex, int[] packCounts, int totalNeeded)
{
    if (packSizeIndex >= packSizes.Length) return new List<int[]>();

    var currentPackSize = packSizes[packSizeIndex];
    var currentPacks = new List<int[]>();

    if (packSizeIndex + 1 == packSizes.Length) {
        var lastOptimal = totalNeeded / currentPackSize;
        packCounts[packSizeIndex] = lastOptimal;
        return new List<int[]> { packCounts };
    }

    for (var i = 0; i * currentPackSize <= totalNeeded; i++) {
        packCounts[packSizeIndex] = i;
        currentPacks.AddRange(GeneratePackingsInternal(packSizes, packSizeIndex + 1, (int[])packCounts.Clone(), totalNeeded - i * currentPackSize));
    }

    return currentPacks;
}

The algorithm is pretty straightforward

1. Loop through every combination of number of 5-packs.
2. Loop through every combination of number of 8-packs, from remaining amount after deducting specified number of 5-packs.
3. etc to 50-packs. For 50-pack counts, directly divide the remainder.
4. Collect all combinations together recursively (so it dynamically handles any set of pack sizes).

Finally, once all the combinations are found, it is pretty easy to find all packs with least waste and least number of packages:

var packSizes = new int[] { 5, 8, 10, 25, 50 };
var totalNeeded = 176;

var result = GeneratePackings(packSizes, totalNeeded);
Console.WriteLine(result.Count());
var maximal = result.Where (r => r.Zip(packSizes, (a, b) => a * b).Sum() == totalNeeded).ToList();
var min = maximal.Min(m => m.Sum());
var minPacks = maximal.Where (m => m.Sum() == min).ToList();

foreach (var m in minPacks) {
    Console.WriteLine("{ " + string.Join(", ", m) + " }");
}

Here is a working example: https://ideone.com/zkCUYZ

Answer 3

This partial solution is specifically for your pack sizes of 5, 8, 10, 25, 50. And only for order sizes at least 40 large. There are a few gaps at smaller sizes that you'll have to fill another way (specifically at values like 6, 7, 22, 27 etc).

Clearly, the only way to get any number that isn't a multiple of 5 is to use the 8 packs.

1. Determine the number of 8-packs needed with modular arithmatic. Since the 8 % 5 == 3, each 8-pack will handle a different remainder of 5 in this cycle: 0, 2, 4, 1, 3. Something like

public static int GetNumberOf8Packs(int orderCount) {
    int remainder = (orderCount % 5);
    return ((remainder % 3) * 5 + remainder) / 3;
}

In your example of 176. 176 % 5 == 1 which means you'll need 2 8-packs.

2. Subtract the value of the 8-packs to get the number of multiples of 5 you need to fill. At this point you still need to deliver 176 - 16 == 160.

3. Fill all the 50-packs you can by integer dividing. Keep track of the leftovers.

4. Now just fit the 5, 10, 25 packs as needed. Obviously use the larger values first.

All together your code might look like this:

public static Order MakeOrder(int orderSize)
{
    if (orderSize < 40)
    {
        throw new NotImplementedException("You'll have to write this part, since the modular arithmetic for 8-packs starts working at 40.");
    }

    var order = new Order();
    order.num8 = GetNumberOf8Packs(orderSize);
    int multipleOf5 = orderSize - (order.num8 * 8);
    order.num50 = multipleOf5 / 50;
    int remainderFrom50 = multipleOf5 % 50;
    while (remainderFrom50 > 0)
    {
        if (remainderFrom50 >= 25)
        {
            order.num25++;
            remainderFrom50 -= 25;
        }
        else if (remainderFrom50 >= 10)
        {
            order.num10++;
            remainderFrom50 -= 10;
        }
        else if (remainderFrom50 >= 5)
        {
            order.num5++;
            remainderFrom50 -= 5;
        }
    }

    return order;
}

A DotNetFiddle