获得最佳组合

Question

我遇到一个问题，即多种产品以不同数量包装在不同的盒子中。每个盒子都由其特定的 ID 来标识。

例如订单是 3 数量的产品 A、6 数量的产品 B 和 15 数量的产品 C。共有 5 盒可用。

CREATE TABLE Orders (
    order_id INT,
    product VARCHAR(255),
    quantity INT
);

INSERT INTO Orders (order_id, product, quantity) VALUES
(101, 'Product A', 3),
(101, 'Product B', 6),
(101, 'Product C', 15);


CREATE TABLE Boxes (
box_id INT,
product VARCHAR(255),
    quantity INT
);

INSERT INTO Boxes (box_id, product, quantity) VALUES
(1, 'Product A', 2), (1, 'Product B', 3), (1, 'Product C', 4),
(2, 'Product A', 2), (2, 'Product B', 6), (2, 'Product C', 1),
(3, 'Product A', 2), (3, 'Product B', 3), (3, 'Product C', 4),
(4, 'Product A', 0), (4, 'Product B', 0), (4, 'Product C', 9),
(5, 'Product A', 0), (5, 'Product B', 3), (5, 'Product C', 6);

基于以上，最好的结果是选择盒子1、3和4，因为我们只需打开3个盒子就可以完成订单。

我已经尝试过这种方法，但如果我有超过 500 个产品，则此方法不可行。

CREATE OR ALTER PROCEDURE FulfillOrderComplex
AS
BEGIN
    DECLARE @RemainingA INT, @RemainingB INT, @RemainingC INT;
    SET @RemainingA = 3; -- Example order requirements
    SET @RemainingB = 6;
    SET @RemainingC = 15;

    -- Temporary table to track box selections
    CREATE TABLE #SelectedBoxes (box_id INT);

    -- Logic to select boxes
    WHILE (@RemainingA > 0 OR @RemainingB > 0 OR @RemainingC > 0)
    BEGIN
        -- Find the box that maximizes the reduction of remaining quantities
        DECLARE @BestBox INT;
        SELECT TOP 1 @BestBox = box_id FROM Boxes
        WHERE (quantity >= @RemainingA AND product = 'Product A') OR
              (quantity >= @RemainingB AND product = 'Product B') OR
              (quantity >= @RemainingC AND product = 'Product C')
        ORDER BY (CASE WHEN product = 'Product A' THEN @RemainingA - quantity
                       WHEN product = 'Product B' THEN @RemainingB - quantity
                       WHEN product = 'Product C' THEN @RemainingC - quantity END);

        -- Update remaining requirements
        UPDATE @RemainingA, @RemainingB, @RemainingC based on @BestBox contents;

        -- Add @BestBox to selected boxes
        INSERT INTO #SelectedBoxes VALUES (@BestBox);

        -- Avoid selecting the same box again
        DELETE FROM Boxes WHERE box_id = @BestBox;
    END

    -- Return the selected boxes
    SELECT box_id FROM #SelectedBoxes;
END;

有人可以帮助我编写一个 SQL 查询，为我提供要打开的箱子 ID 来完成订单，同时确保打开最少数量的箱子，无论订单包含多少产品。

Answer 1

您正在可能性树中寻找最佳分支：在每一步寻找最佳节点的算法并不能保证找到最佳分支：“不太好”的节点可能会隐藏以下节点“非常好的分支”... 生成框的组合将是成本最高的：您必须比较覆盖元组给出最佳解决方案的顺序的所有 C(n,p)，并且最有效的算法使用 2 的幂来实现它，它将框的数量限制为数据库可以处理的最大 2 次方，除非使用其他算法，否则产品的数量不成问题。 要获取覆盖框组的列表：

（CTE1）首先计算盒子中每个（订单，产品）的数量，

(CTE2) 只保留能满足的订单，报告其他的

(CTE3)计算每个框的行数的2的幂

(CTE4) 使用 2^rownum 算法计算框之间的 C(n,p) 元组

(CTE5) 将每个元组成员连接到它代表的框，检查顺序（CTE2 中的顺序）是否满足，返回相应的元组

解决方案：根据你的标准计算每个返回元组的“质量”

CTE5 的示例结果，其中质量将是最小的框数：

1,3,4       3   101 1
1,2,3,5     4   101 2
1,2,4,5     4   101 2
1,3,4,5     4   101 2
2,3,4,5     4   101 2
1,2,3,4     4   101 2
1,2,3,4,5   5   101 3

最新列是元组升序基数（第 2 列）的密集排名。

虽然基于“最佳”节点的算法（例如，根据使用的产品数量“最佳”......）可能会给出解决方案：4,2,5,1。