没有放假之前就从网上订了一本《算法竞赛入门经典》（lrj著），里面的内容确实是“入门”，不过有许多东西之前都不了解，通读了一遍，收获确实挺大。
今天刚起床（我十点钟才起床），就打开电脑，准备把“集合上的动态规划”那道例题自己编写一下。lrj在书中是用递推的形式，但是我思考了一下，那样做不太好。第一，要处理的对象是“集合”，通过记忆化形式的递归逐步缩小集合的规模显然要比递推写起来顺手很多；第二，递推计算了许多不必要的状态（这也是记忆化搜索的优势），很显然的一个事实就是状态只有在集合S中元素个数为偶数的时候才有意义，而元素为奇数的情况在递推时也被计算出。
以下是我的代码：
#include<stdio.h>
#include<math.h>
#include<string.h>
const long maxn=22;
const double INF=20000007.0;
typedef struct
{
long x,y,z;
}point;
long n,s;
double d[(1<<maxn)+7];
point p[maxn];
double min(double a,double b)
{
return (a<b?a:b);
}
double dist(point &a,point &b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double dp(long s)
{
long i,j;
if(d[s]!=-1) return d[s];
d[s]=INF;
for(i=0;i<n;i++)
if(s&(1<<i))
break;
for(j=i+1;j<n;j++)
if(s&(1<<j))
d[s]=min(d[s],dp(s^(1<<i)^(1<<j))+dist(p[i],p[j]));
return d[s];
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
scanf("%ld",&n);
for(long i=0;i<n;i++)
scanf("%ld%ld%ld",&p[i].x,&p[i].y,&p[i].z);
// Input
s=0;
for(long i=1;i<=n;i++)
{
s*=2;s+=1;
}
printf("%ld\n",s);
for(long i=0;i<=s;i++) d[i]=-1;
d[0]=0;
// Init
printf("%.3lf\n",dp(s));
// DP & Output
return 0;
}
因为没有data，也不知道会不会有些地方因为没有注意而写错，如果有，还请指出修正。
下面是我自己构造的一组数据：
Input：
20
1 2 3
1 1 1
5 6 2
4 7 8
2 3 1
1 4 7
2 5 8
3 6 9
1 2 5
2 3 6
4 5 2
7 8 5
4 5 1
-1 2 3
-1 -9 -7
0 0 0
100 0 0
9 5 1
7 5 3
5 5 5
Output：
119.076
posted on 2010-02-11 10:57
lee1r 阅读(2016)
评论(0) 编辑 收藏 引用 所属分类:
Programming Diary