沒有放假之前就從網上訂了一本《算法競賽入門經典》（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 閱讀(2107)
評論(0) 編輯 收藏 引用 所屬分類:
Programming Diary