我正試圖找到一個最優算法,可以找到最大的子集,其中元素的總和最低,同時覆蓋所有元素。需要一個算法來查找元素子集中的最小代價
例如: - 想象一下A B C是零售商,W X Y Z是產品,目標是儘量減少訪問次數,降低價格。
A B C
W 4 9 2
X 1 3 4
Y 9 3 9
Z 7 1 1
So it appears my top two choices are
a) B:{XYZ} - 7 C:{W} - 2
b) C:{WXZ} - 7 B:{Y} - 3
So a) is picked because since it has a lower cost, i.e 9.
這個問題看起來類似於頂點覆蓋和其他線性規劃算法,但我找不出合適的。
更新:
看來我需要添加一個額外的變量。介紹t。如果訪問最少的零售商和最少的零售商的成本> t,則選擇下一個前者。
Continuing with the example.
say t = 5,
The largest subset containing all elements would be B:{WXYZ} with a cost of 16.
The next largest subset(s) is B:{XYZ} - 7 C:{W} - 2 with a cost of 9.
t = 16 - 9 > 5. So we pick B:{XYZ} - 7 C:{W} - 2
but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5.
So B:{XYZ} - 7 C:{W} - 2 is picked
真的,我只是有興趣,如果已經有一個適合這種模式的算法。我不能成爲需要這種優化的第一人。
Hrmm,考慮使用樹,也許深度優先搜索?過了一段時間,因爲我做了這樣的事情,似乎它可以工作。 – Trent
什麼是最小化價格和最小化訪問之間的折中。您是否想以最低的價格找到滿足這些要求的最低訪問次數? – Owen
這個問題看起來像http://en.wikipedia.org/wiki/Transportation_theory_(mathematics) – MBo