Dies ähnelt meinem Frage .
Wie in der Antwort von @Origin ausgeführt, handelt es sich um ein Set-Coverage-Problem und ist ein NP-Complete Problem, d.h. unberechenbar für alle außer einer sehr kleinen Anzahl von Möglichkeiten.
Für Ihr Problem kann eine Greedy-Algorithmus-Lösung angemessen sein.
Ich habe keine Zeit, Ihr Problem zu lösen, aber unten ist der Code, den ich verwendet habe, um meins zu lösen. Ihre Tabellenstruktur ist einfacher, Ihre Lösung sollte es auch sein!
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
