更理论的方法是证明你的问题 似物质的 结构。如果你能够证明你的问题有这样的结构,那么就有一个贪婪的算法来解决它。
根据经典书 "算法介绍" 矩阵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.
通常也有一个权重函数,在s中分配每个元素x,一个权重。
如果你可以将你的函数定义为加权矩阵,那么下面的像金字塔一样的伪代码可以解决你的问题:
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}
能不能不那么数学化?