mysqlを使用して必要な数量を満たす

これは私の質問 。

@Originの回答で指摘されているように、これは集合被覆問題です NP完全 です。 問題、つまり、ごく少数の可能性を除いて計算できない。

あなたの問題には、欲張りアルゴリズムの解決策が適切かもしれません。

私はあなたの問題を解決する時間がありませんが、以下に私が私の問題を解決するために使用したコードが投稿されています。テーブルの構造は単純なので、ソリューションも単純である必要があります！

DECLARE @GreedySetCover table
(
    Location_Id int
    ,Supplier_Id int
    ,Ranking int
)

INSERT INTO @GreedySetCover
--Include Suppliers who are sole suppliers for any item
SELECT  ss.Location_Id
        ,si.Supplier_Id
        ,0 Ranking
FROM    (
        SELECT  pr.Location_Id
                ,pr.Item_Id
        FROM    PartsRequests pr
                INNER JOIN
                SupplierItems si ON pr.Item_Id=si.Item_Id
        WHERE   pr.Order_Id IS NULL
        GROUP BY    pr.Location_Id
                    ,pr.Item_Id
        HAVING  COUNT(*)=1
        ) ss
        INNER JOIN
        SupplierItems si ON si.Item_Id=ss.Item_Id
UNION
--Include suppliers who do not charge a delivery fee
SELECT  pr.Location_Id
        ,si1.Supplier_Id
        ,0 Ranking
FROM    PartsRequests pr
        INNER JOIN
        SupplierItems si1 ON si1.Item_Id=pr.Item_Id
WHERE   pr.Order_Id IS NULL
        AND
        (
        NOT EXISTS
        (SELECT ISNULL(si2.AmountPerOrder,0)
        FROM    SupplierItems si2
        WHERE   si1.Supplier_Id=si2.Supplier_Id
                AND
                si2.Item_Id=0)
        OR
        (SELECT ISNULL(si2.AmountPerOrder,0)
        FROM    SupplierItems si2
        WHERE   si1.Supplier_Id=si2.Supplier_Id
                AND
                si2.Item_Id=0
        )=0
        )


DECLARE @Ranking int = 1
--While any item does not have a supplier
WHILE   EXISTS 
        (
        SELECT  pr.Location_Id
                ,pr.Item_Id
        FROM    PartsRequests pr
                EXCEPT  
                (
                SELECT  gsc.Location_Id
                        ,pr1.Item_Id
                FROM    @GreedySetCover gsc
                        INNER JOIN
                        SupplierItems si ON gsc.Supplier_Id=si.Supplier_Id
                        INNER JOIN
                        PartsRequests pr1 ON pr1.Item_Id=si.Item_Id AND pr1.Location_Id=gsc.Location_Id
                WHERE pr1.ORDER_ID IS NULL
                )
        )
BEGIN
    --Get the supllier whcovere uncovered items at the lowest cost
    INSERT INTO @GreedySetCover
    SELECT  sort.Location_Id
            ,sort.Supplier_Id
            ,@Ranking 
    FROM    (
            SELECT  uncovered.Location_Id
                    ,si.Supplier_Id
                    ,ROW_NUMBER() OVER 
                        (PARTITION BY uncovered.Location_Id
                         ORDER BY   
                         --This is the weighting function 
                         SUM(uncovered.Quantity*si.Price) +         --The cost of the Items
                         (SELECT    ISNULL(si2.AmountPerOrder,0)    --Plus the delivery fee
                          FROM      SupplierItems si2
                          WHERE     si.Supplier_Id=si2.Supplier_Id
                                    AND
                                    si2.Item_Id=0)
                         /cast(COUNT(*) as float)) RowNum           --Divided by the number of items covered
            FROM    (
                    SELECT pr.Location_Id
                          ,pr.Item_Id
                          ,pr.Quantity
                    FROM    PartsRequests pr
                            --Remove uncovered items
                            EXCEPT  
                            (
                            SELECT  gsc.Location_Id
                                    ,pr1.Item_Id
                                    ,pr1.Quantity
                            FROM    @GreedySetCover gsc
                                    INNER JOIN
                                    SupplierItems si ON gsc.Supplier_Id=si.Supplier_Id
                                    INNER JOIN
                                    PartsRequests pr1 ON pr1.Item_Id=si.Item_Id AND pr1.Location_Id=gsc.Location_Id
                            WHERE pr1.ORDER_ID IS NULL
                            )
                    ) uncovered
                    INNER JOIN
                    SupplierItems si ON si.Item_Id=uncovered.Item_Id
            GROUP BY Location_Id, Supplier_Id
            ) sort
    WHERE RowNum = 1

    SET @[email protected]+1
END

--SELECT    *
--FROM  @GreedySetCover
--ORDER BY  Ranking 
--          ,Location_Id

SELECT  Location_Id
        ,Supplier_Id
        ,Number
        ,Quantity
        ,Price
FROM    (
        SELECT  pr.Id PartsRequest_Id
                ,pr.Item_Id
                ,pr.Quantity
                ,pr.RequestTime
                ,pr.Location_Id
                ,pr.Person_Id
                ,pr.Order_Id
                ,si.Supplier_Id
                ,si.Number
                ,si.Price
                ,si.AmountPerOrder      
                ,ROW_NUMBER() OVER (PARTITION BY gsc.Location_Id,pr.Item_Id
                                    ORDER BY si.Price) RowNum
        FROM    @GreedySetCover gsc
                INNER JOIN  
                PartsRequests pr ON gsc.Location_Id=pr.Location_Id
                INNER JOIN
                SupplierItems si ON gsc.Supplier_Id=si.Supplier_Id
                                    AND
                                    pr.Item_Id=si.Item_Id
        ) Results
WHERE   RowNum=1
UNION
SELECT  gsc.Location_Id
        ,si.Supplier_Id
        ,si.Number
        ,si.AmountPerOrder
        ,Price
FROM    @GreedySetCover gsc
        INNER JOIN
        SupplierItems si ON gsc.Supplier_Id=si.Supplier_Id
WHERE   AmountPerOrder>0
ORDER BY    Location_Id
            ,Supplier_Id
            ,Number