沒有放假之前就從網(wǎng)上訂了一本《算法競賽入門經(jīng)典》（lrj著），里面的內(nèi)容確實是“入門”，不過有許多東西之前都不了解，通讀了一遍，收獲確實挺大。
今天剛起床（我十點鐘才起床），就打開電腦，準(zhǔn)備把“集合上的動態(tài)規(guī)劃”那道例題自己編寫一下。lrj在書中是用遞推的形式，但是我思考了一下，那樣做不太好。第一，要處理的對象是“集合”，通過記憶化形式的遞歸逐步縮小集合的規(guī)模顯然要比遞推寫起來順手很多；第二，遞推計算了許多不必要的狀態(tài)（這也是記憶化搜索的優(yōu)勢），很顯然的一個事實就是狀態(tài)只有在集合S中元素個數(shù)為偶數(shù)的時候才有意義，而元素為奇數(shù)的情況在遞推時也被計算出。
以下是我的代碼：
#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，也不知道會不會有些地方因為沒有注意而寫錯，如果有，還請指出修正。
下面是我自己構(gòu)造的一組數(shù)據(jù)：
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 閱讀(2077)
評論(0) 編輯 收藏 引用 所屬分類:
Programming Diary