집합 상의 동적 계획 - 최 적 화 된 배합 문제 (추천: * * * *)

/*

    :  

   《        》,        ---      
  :    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        ,      ,        2。               ,       。

   :            ,       n      ,          ,                。

  :①       ,         ,       。
*/


//   :  。。。
#include <cstdio>
#include <cstring>
#include <cmath>
const int nMax=21;
const double INF=1e10;
int n;
struct Node
{
	int x,y,z;
}node[nMax];
double d[nMax][1<<nMax];
void init()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d %d %d",&node[i].x,&node[i].y,&node[i].z);
}
double min(double a,double b)
{
	return a<b?a:b;
}
double dis(Node &a,Node &b)//①
{
	return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
void solve()
{
	for(int i=0;i<n;i++)
	{
		for(int s=0;s<(1<<(i+1));s++)
		{
			if(s==0) d[i][s]=0;
			else d[i][s]=INF;
			if((s & (1<<i)))
			{
				for(int j=i-1;j>=0;j--)
				if((s & (1<<j)))
					d[i][s]=min(d[i][s],dis(node[i],node[j])+d[i-1][s^(1<<i)^(1<<j)]);
			}
			else if(i!=0)
			{
				d[i][s]=d[i-1][s];
			}
		}
	}
}
int main()
{
	freopen("f://data.in","r",stdin);
	init();
	solve();
	printf("%.3lf
",d[n-1][(1<<n)-1]); return 0; } // : 。。。 //#define TEST #include <cstdio> #include <cstring> #include <cmath> const int nMax=21; const double INF=1e10; int n,S; struct Node { int x,y,z; }node[nMax]; double d[1<<nMax]; void init() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d %d %d",&node[i].x,&node[i].y,&node[i].z); S=1<<n; for(int i=1;i<S;i++) d[i]=-1; d[0]=0; } double min(double a,double b) { return a<b?a:b; } double dis(Node &a,Node &b) { return sqrt((double)(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(int p) { if(d[p]!=-1) return d[p]; d[p]=INF; int i,j; for(i=n-1;i>=0;i--) if(p & (1<<i)) break; for(j=i-1;j>=0;j--) if(p & (1<<j)) d[p]=min(d[p],dis(node[i],node[j])+dp(p^(1<<i)^(1<<j))); #ifdef TEST printf("%d %d
",p,d[p]); #endif return d[p]; } int main() { freopen("f://data.in","r",stdin); init(); printf("%.3lf
",dp(S-1)); return 0; } // : #include <cstdio> #include <cstring> #include <cmath> const int nMax=21; const double INF=1e10; int n,S; struct Node { int x,y,z; }node[nMax]; double d[1<<nMax]; void init() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d %d %d",&node[i].x,&node[i].y,&node[i].z); S=1<<n; d[0]=0; } double min(double a,double b) { return a<b?a:b; } double dis(Node &a,Node &b) { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)); } void solve() { for(int s=1;s<S;s++) { int i,j; d[s]=INF; for(i=n-1;i>=0;i--) if(s & 1<<i) break; for(j=i-1;j>=0;j--) if(s & 1<<j) d[s]=min(d[s],dis(node[i],node[j])+d[s^(1<<i)^(1<<j)]); } } int main() { freopen("f://data.in","r",stdin); init(); solve(); printf("%.3lf
",d[S-1]); return 0; }

테스트 데이터:
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
참고 블 로그:http://www.cppblog.com/rakerichard/archive/2010/02/11/107696.html

좋은 웹페이지 즐겨찾기