하밀(hamil) 문제를 다이나믹으로 풀기
코덕질/해탈내역들 2010/07/09 12:18
#include "stdio.h"
int table[1000000][10]; // [상태][레벨]
int map[20][20];
int size;
int limit;
inline int min(int a, int b)
{
if (a<b) return a; else return b;
}
void input()
{
int i,j;
scanf("%d", &size);
for (i=0; i<size; i++)
for (j=0; j<size; j++)
scanf("%d", &map[i][j]);
limit = (1<<size);
}
void proc()
{
int i,j,k,l;
// init
for (i=0; i<size; i++) {
table[(1<<i)][0]=map[0][i];
}
// from level 1
for (i=1; i<size; i++) {
for (j=(1<<i)-1; j<limit; j++) {
for (k=0; k<size; k++) if (!(j<<k&i) && table[j][i-1]>0 && map[i][k]>0) {
if (table[j][i]==0) table[j][i]=0x7fffffff;
table[j][i] = min(table[j][i], table[j][i-1]+map[i][k]);
}
}
}
// at final level
res = 0x7fffffff;
for (j=(1<<size)-1; j<limit; j++) {
if (table[j][size]>0 && map[size][0]>0) {
res = min(res, );
}
}
}
void output()
{
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
input();
proc();
output();
return 0;
}
아직 소스코드 수정 안됨.
하밀을 다이나믹으로 풀면 다이나믹의 특성상 상당히 연산속도가 빠르다. 백트래킹으로는 12정도의 테이블까지 수용이 가능했던가.. 다이나믹은 19까지 수용이 가능하다.
물론 메모리 사용률은 두말할 것 없고 연산시간도 최악의 값의 경우에는 엄청나기는 매한가지다 -_-;.. 1초당 10억번 연산이 가능한 컴퓨터에게는 꽤 이래저래 최선이면서도 악독한 연산을 수행시키는 알고리즘.
댓글을 달아 주세요