/*
提醒推荐:五星
刘汝佳《算法竞赛入门经典》,集合上的动态规划---最优配对问题
题意:空间里有n个点P0,P1,...,Pn-1,你的任务是把它们配成n/2对(n是偶数),使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。
状态:d(i,S)表示把前i个点中,位于集合S中的元素两两配对的最小距离和
状态转移方程为:d(i,S)=min{|PiPj|+d(i-1,S-{i}-{j}}
书上的解法有些问题,正解见方法一
方法二:状态可以进行压缩,i的值其实隐藏在S中,S中最高位为1的即为i,所以需要一次查找,从n-1到0进行一次历编即可,整个运算下......
阅读全文