求解,一道相似度排序的问题.
假设有一个数组(长度任意):
[A,B,C,D]
任意2个元素之间的相似度已知,可用W[x,y]来表示.
假设[A,B,C,D]的任何一个排序称为: [X,Y,Z,W]
那么 Value(X-Y-Z-W) = W[X,Y] + W[Y,Z] + W[Z,W] . // 相邻的W值相加.
很明显 总会有一个排序使得Value值最大.
问题就是求这个排序了.
PS : 暴力枚举就免了哈,枚举的复杂度高了点. 求一个尽可能的快一点的方法.
顺便,不要求Value一定要最大,但是要一个尽可能大(也就是相当于尽可能的有优化,最坏的情况也不会是minValue)
[解决办法]
可以先列出所有的二子集 然后计算出所有的二子集中你说的距离 然后用贪心算法试一下 我只是觉得这个思路貌似可以 你试一下
[解决办法]
一看到最大我最先想到的也是贪心