글 읽기 - 비트마스크 메모리 초과(c언어)

cksdnwh 5년 전 0

카테고리가 비트마스크라고 돼있어서 비트마스크 + 다이나믹 프로그래밍 방식으로 접근을 해봤습니다.

double dp[20][1<<20];

n이 최대일 때가 20이므로 위와 같이 선언을 해야됩니다.

근데 사용되는 메모리를 구해보면 8*20*(1<<20) = 167,772,160 byte가 나오게 되어 문제에서 제한된 메모리를 초과하게 됩니다.

비트마스크로 풀 수 있는 다른 방식이 있나요??

#include<stdio.h>
#include<string.h>


int n;
int p[20][20];
double dp[20][1 << 20];

double max(double a, double b) {
	return a > b ? a : b;
}

double find(int agent, int task) {

	if (agent == n)
		return 1;

	if (dp[agent][task] != -1)
		return dp[agent][task];
	
	dp[agent][task] = -10000;

	for (int i = 0; i < n; i++) {
		if (!(task & 1 << i)) {
			dp[agent][task] = max(dp[agent][task], find(agent + 1, task | 1 << i)*((double)p[agent][i]/(double)100));
		}
	}
	return dp[agent][task];
}

int main(void) {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &p[i][j]);
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 1<<n; j++)
			dp[i][j] = -1;


	printf("%f", find(0, 0)*100);
}

startlink 5년 전 1

[20]이 꼭 필요할까요

cksdnwh 5년 전 0

흠 그런가요.. 다시 생각해보겠습니다 감사합니다!

startlink 5년 전 1

아마 외판원 순회를 푼 기억 때문에 [20]을 추가한 느낌인데, 이 문제는 [20]이 필요 없죠

cksdnwh 5년 전 0

곰곰이 생각해보니까 그렇네요

감사합니다!! 해결했네요~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

비트마스크 메모리 초과(c언어)

cksdnwh 5년 전 0

startlink 5년 전 1

cksdnwh 5년 전 0

startlink 5년 전 1

cksdnwh 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말