Clever Geek Handbook

Packaging material from a set of available bags

Suppose that the customer Item is ordered - in this case, it turns out that he is ordering 176 ( totalNeeded

) of this Item .

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

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

...

A rough way of packaging 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 result will be:

You need : 3 x 50 bags, 1 x 25 bags, 1 x 5 bags

Total items : 180

Excess = 4 elements; 180 - 176

The above is not that hard to code, I work locally. However, this is not the best way to pack this item. Note: "best" means the least amount of excess.

So ... we have 8 packages, we need 176. 176/8 = 22. Send 22 x 8 packages to the customer, they will get exactly what they need. Again, this is even simpler than the pseudocode I wrote ... let's see if the total is evenly divisible by any of the packets in the array - if so, "at least" we know we can return 22 x 8 packages are accurate.

In the case where the number is not divisible by the array value, I am trying to figure out a possible way so that the array values ​​can be concatenated to achieve at least the desired number (176), and then evaluate the different combinations using the Number of packets needed in total.

If anyone has any readings to do on this topic or advice of any kind to get me started, we would greatly appreciate it.

thank

+3


source to share


3 answers


If this example problem really reflects the real problem you are solving, it is small enough to try every brute-force combination using recursion. For example, I found exactly 6,681 unique packs that are locally maximized and for a total of 205 have exactly 176 items in common. A (unique) solution with a minimum number of packets of 6, which is {2-8, 1-10, 3-50}. The total execution time for the algorithm was 8ms.

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 simple

  • Scroll through each combination of the 5 packs.
  • Scroll through each 8-pack combination, starting with the remaining amount after subtracting the specified number of 5-packs.
  • etc. up to 50 packages. For 50 burst samples, divide the remainder.
  • Collect all combinations together recursively (so that it dynamically handles any set of packet sizes).


Finally, once all the combinations have been found, it is fairly easy to find all the packages with the 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's a working example: https://ideone.com/zkCUYZ

+2


source


This is a variant of Subset Sum Problem (optimization version)

While the problem is NP-Complete, there is a fairly efficient pseudo-polynomial-time Dynamic Programming solution by following the recursive formula:

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

Dynamic Programming Solution will create a table in which the item D[x][i]==true

, if you can use the first i

types of packages to set the amount x

.
Needless to say, D[x][n] == true

if there is a solution with all available packages summarizing on x

. (where n

is the total number of packages you have).



To get the "closest largest number", you simply need to create a size table W+pack[0]-1

( pack[0]

which is the smallest package available W

- this is the amount you are looking for) and select the value that gives you the true

closest to W

.

If you want to assign different values ​​to different types of packages, it would be a backpack problem that is very similar - but uses simple true / false values ​​instead.

Retrieving the actual "items" (bundles) selected after that is done by returning the table and re-checking your steps. This thread and this thread detail how to achieve this with more details.

+3


source


This is a partial solution specifically for your bag sizes 5, 8, 10, 25, 50

. And only for order sizes of at least 40 large . There are some smaller spaces that you will need to fill in in a different way (in particular with values ​​such as 6, 7, 22, 27

, etc.).

Clearly, the only way to get any number other than 5 is to use 8 packets.

  • Determine the number of 8-packs needed with modular arithmetic. Since 8 % 5 == 3

    each 8-package will handle the other residue 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, 176. 176 % 5 == 1

, which means you need 2 8-Packs.

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

    .

  2. Complete all 50 packages that you can divide by whole numbers. Watch out for leftovers.

  3. Now just place the packages 5, 10, 25

    as needed. Obviously use large values ​​first.

Your entire 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

0


source






More articles:


All Articles