집합상의 동적 기획

22529 단어 동적 기획
예제: 가장 좋은 배합 문제
공간에 n개의 점 P0, P1,......Pn-1, 당신의 임무는 그들을 n/2쌍 (n은 짝수) 으로 배합하여 각 점이 한 점 맞도록 하는 것입니다.모든 점 대 중 두 점의 거리의 합은 가능한 한 작아야 한다.n<=20,|xi|,|yi|,|zi|<=1000.
샘플 입력:
201 2 31 1 15 6 24 7 82 3 11 4 72 5 83 6 91 2 52 3 64 5 27 8 54 5 1-1 2 3-1 -9 -70 0 0100 0 09 5 17 5 35 5 5
분석:
각 점이 짝을 지어야 하기 때문에 문제를 다음과 같은 다단계 결정 과정으로 보기 쉽다. 먼저 P0과 누가 짝을 지어야 하는지를 확정한 다음에 P1, 다음은 P2,......, 마지막은 Pn-1.앞의 사고방식에 따라 d(i)를 설정하면 앞의 i점 두 개를 짝짓는 최소 거리와 그 다음에 i점의 결정을 고려한다. 이것은 누구와 짝짓기를 합니까?가령 그것이 점 j와 짝짓기(j상태를 옮길 수 없다는 것을 발견한 후 흔히 볼 수 있는 방법은 차원, 즉 새로운 요소를 증가하고 상태를 더욱 세밀하게 묘사하는 것이다.방금'어떤 원소를 제외하고'는 언급했으니 상태의 일부분으로 삼아도 무방하다. d(i, S)를 설정하면 앞의 i점에서 집합 S에 있는 원소 두 쌍을 짝짓기하는 최소 거리를 나타낸다. 그러면 상태 이동 방정식은 다음과 같다.
d (i, S) = min {|Pipj|+ d (i-1, S-{i}-{j}) | j는 S}에 속함
여기서 |PiPj는 Pi와 Pj 사이의 거리를 나타냅니다.경계는 d (-1, S) = 0.
기억 검색의 코드는 다음과 같습니다.
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #define maxn 20
 5 #define INF (1<<30)
 6 int n;
 7 struct Point{
 8     double x, y, z;
 9 } p[maxn];
10 double f[(1<<maxn)];
11 inline double dist(int i, int j)
12 {
13     return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y) + (p[i].z-p[j].z)*(p[i].z-p[j].z));
14 }
15 inline double min(double x, double y)
16 {
17     if(x < y) return x; 
18     return y;
19 }
20 double d(int S){
21     //           ！！（         ！！ ）
22     if(f[S] != -1) return f[S];
23     int i, j;
24     double& ans = f[S];
25     ans = (S == 0? 0 : INF);
26     for(i = n-1; i >= 0; --i) if(S & (1<<i)) break;
27     for(j = 0; j < i; ++j) if(S & (1<<j))
28       ans = min(ans, d(S^(1<<i)^(1<<j)) + dist(i, j));
29     return ans;
30 }
31 
32 int main(){
33     int i;
34     scanf("%d", &n);
35     if(n%2) {printf("No answer!
"); return 0;}
36     for(i = 0; i < n; ++i) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
37     for(i = 0; i < (1 << n); ++i) f[i] = -1;
38     printf("%.3lf
", d((1<<n)-1));
39     /*
40     int cnt = 0;
41     for(i = 0; i < (1 << n); ++i) if(f[i]!=-1) ++cnt;
42     printf("%d
", cnt);
43     */
44     return 0;
45 }

동적 계획 코드는 다음과 같습니다.
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #define maxn 20
 5 #define INF (1<<30)
 6 int n;
 7 struct Point{
 8     double x, y, z; 
 9 } p[maxn];
10 double f[maxn][(1<<maxn)];   
11 inline double dist(int i, int j)
12 {
13     return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y) + (p[i].z-p[j].z)*(p[i].z-p[j].z));
14 }
15 inline double min(double x, double y)
16 {
17     if(x < y) return x; 
18     return y;
19 }
20 int main(){
21     int i,j;
22     scanf("%d", &n);
23     if(n%2) {printf("No answer!
"); return 0;}
24     for(i = 0; i < n; ++i) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);   
25     for(i = 0; i < n; ++i)
26         for(int S = 0; S < (1 << (i+1)); ++S){
27             double& ans = f[i][S];
28             ans = (S==0 ? 0 : INF);
29             if(S & (1 << i)) {
30                 for(j = 0; j < i; ++j) if(S & (1 << j))
31                     ans = min(ans, f[i-1][S^(1<<i)^(1<<j)] + dist(i, j));
32             }
33             else if(i!=0) f[i][S] = f[i-1][S];  
34         }    
35         printf("%.3lf
", f[n-1][(1<<n)-1]);
36         return 0;
37 }

 
은연중 단계
위의 방정식은 한층 더 간소화할 수 있다.사실 단계 i는 저장할 필요가 없다. 이것은 이미 S에 숨겨져 있다. S에서 가장 큰 요소는 i이다.이렇게 하면 "S의 원소를 두 쌍으로 짝짓는 최소 거리와"를 직접 d(S)로 표시하면 상태 전이 방정식은 다음과 같다.
d(S)=min{|Pipj|+d(S-{i}-{j})|j는 S에 속하고 i=max(S)}
상태는 2n개이고 각 상태는 O(n)종의 전이 방식이 있으며 총 시간 복잡도는 O(n2n)이다. 
특히 많은 사람들이 이런 상태로 방정식을 옮기고 있다.
d(S) =min{|Pipj|+d(S-{i}-{j}) | i, j는 S}
그것은 아까의 방정식과 매우 유사한데, 유일하게 다른 것은 i와 j는 모두 매거해야 한다는 것이다.이렇게 하는 것도 맞지만 각 상태의 이동 횟수는 O(n2)에 달하고 전체 시간의 복잡도는 O(n22n)로 아까의 방법보다 느리다.이 예는 같은 상태 묘사를 사용하면 결정을 줄이는 것도 중요하다는 것을 설명한다.
그러면 어떻게 S 중의 가장 큰 원소를 구할 수 있습니까?하나의 순환으로 판단하면 된다.S가 {0,1,2,..., n-1}의 모든 서브집합을 다 찾았을 때 평균 판단 횟수는 2에 불과합니다.
1 for(int S=0; S<(1<<n); S++)
2 {
3     int i,j;
4     d[S] = INF;
5     for(i=0; i<n; i++)
6         if(S && (1<<i)) break;
7     for(j=i+1; j<n; j++)
8         if(S & (1<<j)) d[S] <?= d[S^(1<<i)^(1<<j)] + dist(i, j));
9 }

상기 프로그램에서 구한 i는 S의 최소 요소이지 최대 요소가 아니지만 답안에 영향을 주지 않는다.또한 j의 매거는 i+1부터 시작한다. i가 S에서 가장 작은 원소인 이상 다른 원소는 자연히 i보다 크다는 것을 의미한다.마지막으로 설명해야 할 것은 S의 매거 순서다.발견하기 어렵지 않다. 만약에 S'가 S의 진짜 서브집합이라면 반드시 S'만약 S'가 S의 진짜 서브집합이라면 반드시 S'최적화 후 코드는 다음과 같습니다.
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #define maxn 22
 5 #define maxs (1<<maxn)
 6 #define INF 1e10
 7 int n; 
 8 double f[maxs], x[maxn], y[maxn], z[maxn];
 9 inline double min(double x, double y)
10 {
11     return x<y?x:y;
12 }
13 inline double dist(int i, int j)
14 {
15     return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) + (z[i]-z[j])*(z[i]-z[j]));
16 }    
17 int main(){
18     scanf("%d", &n);
19     for(int i  = 0; i < n; ++i) scanf("%lf%lf%lf", x+i, y+i, z+i);
20     int U = (1 << n);
21     for(int S = 0; S < U; ++S){
22         int i;
23         for(i = n-1; i >= 0; --i) if(S & (1<<i)) break;
24         f[S] = (S==0) ? 0 : INF;
25         for(int j = 0; j < i ; ++j) if(S & (1<<j)){
26           f[S] = min(f[S], f[S^(1<<i)^(1<<j)] + dist(i, j));
27         }    
28       }
29     printf("%.3lf
", f[U-1]);
30     return 0;
31 }
주간 챌린지 #085 태스크 #2::(Raku)
데이터 구조 - 선형 표 순서 저장

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage