PHP实现基于Qty per Box的订单数量分配（Knapsack算法相关）

问题背景 #

被该问题困扰超2周，已知需用背包类算法但不知如何实现。现有数据如下：

主品类表 #

订单交易表 #

预期需求 #

将订单数量按主品类表的单箱容量拆分到多个箱子，同品类的剩余箱容可承接后续同品类订单，直至填满箱量上限。例如N1的40件P类订单，拆分为3个满箱（12件）+1个4件的箱子；N2的8件P类订单可以填充到这个剩余4件的箱子里，最终这个箱子变成12件满箱，无需额外开新箱。

附PHP格式的JSON数据示例：

[
  [
    {"Customer":"N1","Category":"P","OrderQty":"41","MaxQtyBox":"12"},
    {"Customer":"N2","Category":"P","OrderQty":"8","MaxQtyBox":"12"}
  ],
  [
    {"Customer":"E1","Category":"V","OrderQty":"1","MaxQtyBox":"36"},
    {"Customer":"E1","Category":"V","OrderQty":"1","MaxQtyBox":"36"}
  ]
]

实现思路 #

这个场景属于装箱问题（Bin Packing），和背包算法思路类似但目标相反：我们需要把多个同品类订单尽可能填充到已有的剩余容量箱子中，减少新箱的创建。核心步骤：

• 按品类分组订单，确保只处理同品类的订单和箱子；
• 对每个品类维护一个「待填充箱子列表」，记录每个箱子的剩余容量；
• 遍历该品类的每个订单，先尝试将订单数量填充到已有剩余容量的箱子中，填满后再创建新箱子；
• 最终输出每个箱子的订单分配详情。

PHP代码实现 #

<?php
// 主品类容量配置
$categoryCapacities = [
    'P' => 12,
    'V' => 8
];

// 原始订单数据
$orders = [
    ['Customer' => 'N1', 'Category' => 'P', 'OrderQty' => 40],
    ['Customer' => 'N2', 'Category' => 'P', 'OrderQty' => 8],
    ['Customer' => 'E1', 'Category' => 'V', 'OrderQty' => 40]
];

// 按品类分组订单
$groupedOrders = [];
foreach ($orders as $order) {
    $cat = $order['Category'];
    if (!isset($groupedOrders[$cat])) {
        $groupedOrders[$cat] = [];
    }
    $groupedOrders[$cat][] = $order;
}

// 处理每个品类的装箱逻辑
$result = [];
foreach ($groupedOrders as $category => $catOrders) {
    $boxCapacity = $categoryCapacities[$category];
    $boxes = []; // 存储每个箱子的剩余容量和已分配的订单片段

    foreach ($catOrders as $order) {
        $remainingQty = (int)$order['OrderQty'];
        $customer = $order['Customer'];

        // 先尝试填充已有箱子的剩余容量
        foreach ($boxes as &$box) {
            if ($remainingQty <= 0) break;

            $fillable = min($remainingQty, $box['remaining']);
            if ($fillable > 0) {
                // 添加订单片段到该箱子
                $box['items'][] = [
                    'Customer' => $customer,
                    'Category' => $category,
                    'OrderQty' => $fillable,
                    'MaxQtyBox' => $boxCapacity
                ];
                $box['remaining'] -= $fillable;
                $remainingQty -= $fillable;
            }
        }
        unset($box); // 解除引用

        // 剩余数量需要创建新箱子
        while ($remainingQty > 0) {
            $newBoxQty = min($remainingQty, $boxCapacity);
            $newBox = [
                'remaining' => $boxCapacity - $newBoxQty,
                'items' => [
                    [
                        'Customer' => $customer,
                        'Category' => $category,
                        'OrderQty' => $newBoxQty,
                        'MaxQtyBox' => $boxCapacity
                    ]
                ]
            ];
            $boxes[] = $newBox;
            $remainingQty -= $newBoxQty;
        }
    }

    // 提取每个箱子的订单片段，整理到结果中
    foreach ($boxes as $box) {
        $result[] = $box['items'];
    }
}

// 输出JSON格式结果
echo json_encode($result, JSON_PRETTY_PRINT);
?>

代码说明 #

1. 分组订单：先把所有订单按品类分组，确保同品类订单一起处理；
2. 填充已有箱子：对于每个订单，先遍历当前品类的待填充箱子，用剩余数量填满箱子的剩余容量；
3. 创建新箱子：当已有箱子无法容纳剩余订单数量时，创建新箱子，每次填充最大可能的数量（不超过箱容）；
4. 结果输出：最终每个子数组代表一个箱子，包含该箱子里的所有订单片段。

运行上述代码后，针对示例订单的输出结果如下（简化版）：

[
    [
        {"Customer":"N1","Category":"P","OrderQty":12,"MaxQtyBox":12},
        {"Customer":"N1","Category":"P","OrderQty":12,"MaxQtyBox":12},
        {"Customer":"N1","Category":"P","OrderQty":12,"MaxQtyBox":12},
        {"Customer":"N1","Category":"P","OrderQty":4,"MaxQtyBox":12},
        {"Customer":"N2","Category":"P","OrderQty":8,"MaxQtyBox":12}
    ],
    [
        {"Customer":"E1","Category":"V","OrderQty":8,"MaxQtyBox":8},
        {"Customer":"E1","Category":"V","OrderQty":8,"MaxQtyBox":8},
        {"Customer":"E1","Category":"V","OrderQty":8,"MaxQtyBox":8},
        {"Customer":"E1","Category":"V","OrderQty":8,"MaxQtyBox":8},
        {"Customer":"E1","Category":"V","OrderQty":8,"MaxQtyBox":8}
    ]
]

内容的提问来源于stack exchange，提问作者shev