1

我正在使用 mysql 和 php，我需要弄清楚如何满足特定请求的数量：如果这是我的请求表：

request id[pk], custID[fk from customer table], productid[fk in products table], quantites_requested, price_requested 这是advertising_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 select 语句，以便：我可以弥补客户的请求数量？

我希望能够选择构成请求数量的最便宜的总数。

因此，在这种情况下，输出将显示：

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-Complete问题，即除了极少数可能性之外的任何可能性都是不可计算的。

对于您的问题，贪心算法解决方案可能就足够了。

我没有时间解决您的问题，但下面发布的是我用来解决我的问题的代码。您的表结构更简单，因此您的解决方案也应该如此！

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 回答