可用包装集中的包装项目

本文关键字：包装 项目 集中 | 更新日期: 2023-09-27 17:55:21

>假设客户正在订购一件商品 - 在这种情况下，事实证明他们订购了该商品的 176 （totalNeeded）。

数据库有 5 条与此项目关联的记录，该项目可以存储在这些记录中：

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

打包的粗略方法是：

 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
      }

基于上述逻辑，结果将是：

您需要： 3 x 50 包， 1 x 25 包， 1 x 5 包

项目总数： 180

超额 = 4 件; 180 - 176

上面的代码并不难，我让它在本地工作。但是，这并不是包装此物品的最佳方法。注："最佳"是指，最小金额的超额。

因此。。。我们有 8 包可用，我们需要 176 包。176/8 = 22。向客户发送 22 x 8 包，他们将得到他们需要的。同样，这甚至比我编写的伪代码更简单......查看所需的总数是否可被数组中的任何包整除 - 如果是这样，"至少"我们知道我们可以回退到 22 x 8 包是准确的。

在数字不能被数组值整除的情况下，我正在尝试确定数组值可以组合以至少达到我们需要的数字 （176） 的可能方法，然后按 # 对不同的组合进行评分所需的包总数。

我该如何解决这个问题？

可用包装集中的包装项目

这是

子集和问题（优化版本）的变体

虽然问题是NP-Complete，但有一个非常有效的伪多项式时间动态规划解决方案，通过遵循递归公式：

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

动态规划解决方案将构建一个表，其中的元素D[x][i]==true iff 您可以使用前i种包来建立总和x。
不用说，D[x][n] == true有一个解决方案，其中包含所有可用的包，总和为 x .（其中n是您拥有的包总数）。

要获得"最接近的较高数字"，您只需要创建一个大小为 W+pack[0]-1 的表（pack[0]是最小的可用包，W是您正在寻找的总和），然后选择产生最接近W true的值。

如果您希望为不同的包装类型提供不同的值，这将变成背包问题，这是非常相似的 - 但使用值而不是简单的真/假。

获得选择的实际"项目"（包）是通过返回表格并追溯您的步骤来完成的。这个线程和这个线程详细说明了如何实现它。

如果此示例问题真正代表您正在解决的实际问题，那么它足够小，可以使用递归尝试所有暴力破解组合。例如，我找到了 6,681 个本地最大化的独特包装，总共有 205 个包装，总共有 176 个项目。具有最小包装数的（唯一）解决方案为 6，即 { 2-8、1-10、3-50 }。该算法的总运行时间为 8 毫秒。

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;
}

算法非常简单

  1. 循环浏览 5 件装数量的每个组合。
  2. 循环浏览 8 包数量的每个组合，从扣除指定数量的 5 包后的剩余数量开始。
  3. 等到 50 包。 对于 50 件装计数，直接除以剩余部分。
    4. 以
  4. 递归方式将所有组合收集在一起（因此它可以动态处理任何一组包装大小）。
最后，一旦找到所有

组合，就很容易找到所有浪费最少、包装数量最少的包装：

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) + " }");
}

下面是一个工作示例：https://ideone.com/zkCUYZ

此部分解决方案专门针对您的包装尺寸 5, 8, 10, 25, 50 . 并且仅适用于至少 40 大的订单大小。 在较小的尺寸下有一些空白，您必须以另一种方式填充（特别是在6, 7, 22, 27等值下）。

显然，获得任何不是 5 倍数的数字的唯一方法是使用 8 个包。

  1. 使用模块化算法确定所需的 8 件装数量。 自8 % 5 == 3以来，每个 8 块装将处理此循环中 5 的不同余数：0, 2, 4, 1, 3 。 类似的东西 
public static int GetNumberOf8Packs（int orderCount） {    整数余数 = （顺序计数 % 5）;    返回 （（余数 % 3） * 5 + 余数）/3;}

在您的示例中 176。 176 % 5 == 1这意味着您需要 2 个 8 件装。

  1. 减去 8 包的值，得到您需要填充的 5 的倍数。 此时，您仍然需要交付176 - 16 == 160。

    2. 通过

  2. 整数除法填充所有 50 包。 跟踪剩菜。

  3. 现在只需根据需要安装5, 10, 25包即可。 显然，首先使用较大的值。

总之，您的代码可能如下所示：

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;
}

点网小提琴

相关文章：