你怎麼能確定問題展示「貪婪的選擇財產」？

Question

恐怕有可能出現「greedy choice property」可能不適用的情況。

對於任何問題，我只能檢查小數據集。如果對於大型數據集，該屬性會失敗？

我們可以肯定嗎？

Answer 1

一個可能更理論的方式是證明您的問題有一個Matroid結構。如果你能證明你的問題有這樣的結構，那麼有一個貪婪的算法來解決它。

根據經典書"Introduction to Algorithms"擬陣a是一個有序對M =（S，L）其中：

* S is a finite nonemtpy set 
* l is a nonempty family of subsets of S, such that B element of l and 
    A a subset of B than also A is element of l. l is called the independent 
    subsets of S. 
* If A and B are elements of l and A is a smaller cardinality than B, then 
    there is some element x that is in B, but not in A, so that A extended 
    by x is also element of l. That is called exchange property. 

通常也有一個權重函數w S中的每個元素x分配，一個重量。

如果你可以制定你的函數作爲加權擬陣，下面的類Python僞代碼解決您的問題：

GREEDY(M,w): 
    (S,l) = M 
    a = {} 
    sort S into monotonically decreasing order by weight w 
    for x in S: 
     if A + {x} in l: 
     A = A + {x}