程序來優化成本

Question

這是我爲我的一個CS類設置的問題，我有點卡住了。這是問題的總結。

Create a program that will: 
1) take a list of grocery stores and its available items and prices 
2) take a list of required items that you need to buy 
3) output a supermarket where you can get all your items with the cheapest price 

input: supermarkets.list, [tomato, orange, turnip] 
output: supermarket_1 

The list looks something like 
supermarket_1 
$2.00 tomato 
$3.00 orange 
$4.00 tomato, orange, turnip 

supermarket_2 
$3.00 tomato 
$2.00 orange 
$3.00 turnip 
$15.00 tomato, orange, turnip 

If we want to buy tomato and orange, then the optimal solution would be buying 
from supermarket_1 $4.00. Note that it is possible for an item to be bough 
twice. So if wanted to buy 2 tomatoes, buying from supermarket_1 would be the 
optimal solution. 

到目前爲止，我已經能夠把數據集中到數據結構，我希望可以讓我輕鬆地做就可以操作。我基本上有超市的字典，價值會指向另一個字典，其中包含從每個條目到其價格的映射。

supermarket_1 --> [turnip --> $2.00] 
        [orange --> $1.50] 

一種方法是使用蠻力，讓所有組合，並找到滿足爲準解決方案，並找到一個具有最小。到目前爲止，這是我能想到的。 沒有假設兩個項目組合的價格會低於分別購買每個項目的價格。

任何建議，提示，歡迎

Answer 1

尋找特定超市的最佳解決方案是set cover problem的推廣，它是NP完全的。減少如下： 給定集合覆蓋問題的一個實例，只需定義一個成本函數爲每個組合分配1，應用解決問題的算法並獲得集合封面實例的最優解。 （因此，找到最低價格對應於找到最小覆蓋集數。）因此，您的問題是NP-hard，並且您無法期望找到以多項式時間運行的解決方案。

你真的應該實施你提到的蠻力法。我也建議你作爲第一步來做到這一點。如果性能不足，您可以使用MIP公式和CPLEX等求解器嘗試 ，或者您必須採用啓發式方法。

對於一家超市來說，找到一個mixed integer program (MIP)是相當簡單的。設x_i爲產品組合i包含在解決方案中的整數，c_i其成本和w_ij產品j包含在產品組合i中的頻率。然後，你喜歡

sum_i x_i * w_ij >= r_j, 

減少

sum_i x_i * c_i 

受條件限制，其中r_j是多久的產品j需要的數量。

Answer 2

好了，你有一個方法，所以現在實現它讓你有一些作品提交。蠻力解決方案不需要很長時間就可以編碼，那麼您可以獲得一些性能數據，並且可以更深入地考慮問題。猜測在一個大城市的合理購物範圍內的超市數量。創建許多超市記錄並以隨機價格將其鏈接到產品表（這比解決方案更有用）。

運行你的蠻力解決方案。它工作嗎？如果它輸出一個解決方案，'手動'加起來的價格，並列出他們隨機採取的其他三個'超市'記錄，（只是選擇一個數字），表明總數不大或相等。修改列表中項目的價格，以便解決方案不再便宜並重新運行，以便獲得不同的解決方案。

它是如此之快以至於沒有進一步的工作是合理的嗎？如果是這樣，請在報告的結論部分中說明，然後將該批次發佈到您的教授/助教。你理解這個任務，思考它，提出一個解決方案，實施它，用一個有代表性的數據集對其進行測試，從而表明功能是可證明的，性能是足夠的 - 你的任務結束了，去吧，考慮下一個一個在啤酒上。

Answer 3

我不確定你的意思是「蠻力」解決方案。 爲什麼不計算每個超市中物品清單的成本，然後選擇最小值？複雜性將會在O（#items x #supermarkets）中很好。

關於你的數據結構，你也可以簡單地有一個矩陣（2維數組）價格[超] [項目]，並使用ID超市/項目。