Asp*_*Mat 4 algorithm optimization dynamic-programming combinatorics number-theory
假设我有一套A={a_1, a_2, ..., a_n}.我还有一个f:AxA->R从A某个实际值中分配一对的函数.我想提取一个子集S_k的大小k 从A以使其最大程度地提高所有元素的整体成对总和S_k
是否有任何已知的算法可以在合理的时间内完成此操作？多项式/准多项式时间也许？
编辑:工作示例
假设A={a_1,a_2,a_3,a_4}with k=3和f定义为:
f(a_1,a_2)=0,f(a_1,a_3)=0,f(a_1,a_4)=0,f(a_2,a_3)=1,f(a_2,a_4)=5,f(a_3,a_4)=10.
然后,S_k={a_2,a_3,a_4}因为它最大化总和f(a_2,a_3)+f(a_2,a_4)+f(a_3,a_4).(即S_k中所有元素的成对总和)