1

私はmysqlとphpを使用しており、特定のリクエストの数量を満たす方法を考え出す必要があります:これが私のリクエストテーブルの場合:

request id[pk], custID[fk from customer table], productid[fk in products table], quantites_requested, price_requested これは、advertized_products テーブルです。

advertiseid[pk], customerid[fk from customer table], productsid[fk in products table], quantites_advertised, price_advertised

リクエストテーブルにこのレコードがある場合:

1,1,1,10.0,5.00

および宣伝されている量として次のとおりです。

1,2,1,4.00,2.00 -- This means customer id 2 is selling choclates(product id 1), for 4KG's @£2.00
2,3,1,5.00,2.50
3,4,1,1.00,1.00
4,5,1,10.00,6.00

顧客の要求数量を補うことができるように、SQL 選択ステートメントをどのように使用できますか?

要求された数量を構成する最も安い合計を選択できるようにしたかったのです。

したがって、この場合、出力は次のようになります。

2,1,4.00,2.00
3,1,5.00,2.50
4,1,1.00,1.00

したがって、顧客 2、3、および 4 は、4+5+1=10.0 の数量が要求された数量を構成するため、表示されます...また、売り手番号 5 よりも安いです。

SQL テーブルを検索して、要求された金額まで数量を累積的に合計し、使用するのに最も安いものを確認できるように、使用できるクエリはありますか?

あなたの助けと時間をありがとう。

4

1 に答える 1

0

これは私の質問に似ています。

@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 @Ranking=@Ranking+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
于 2013-02-19T03:52:40.193 に答える