글 읽기 - 배낭문제 시간초과에 대해 질문드립니다!!

yousrain 4년 전 0

두 풀이간 시간 차이가 어디서 나는지 여쭤봅니다. 고수님들 부탁드립니다 !!

1) 재귀를 이용한 풀이

int dp[101][100001]을 선언하여

dp[p][q]가 0이 아닌 경우

즉, p번째 보석을 남은 용량이 q인 가방에 넣을 때 최댓값이

이미 계산된 경우는 중복계산하지 않는 방법을 사용했습니다.

이 경우 무난하게 통과할줄 알았는데 이 풀이도 시간초과가 났습니다 ㅠㅠ

2) iterate를 이용한 풀이

재귀호출이 아닌 반복을 이용하여

int dp[101][100001]의 dp[p][q]에서

p번째 보석을 용량이 q인 가방에 넣을 때 dp[p-1]의 값을 참고하여 최댓값을 구하는 알고리즘입니다.

이 방법은 시간초과가 나지 않았습니다.

질문 :

1번 풀이 문제가 직관적으로 몇번의 재귀를 호출할지는 잘 모르겠습니다만,

2번 풀이는 배낭의 크기만큼 반복을 반드시 하는데 반해 1번 풀이는 그렇지 않다는 점에서 1번이 더 효율적으로 보이는데

결과는 반대로 나오네요 ㅠㅠ

글이 두서 없어 죄송합니다. 코드 구현부분만 첨부하니 답변 부탁드립니다!

// 재귀를 이용한 1번 풀이
int knapsack(int pos, int weigh){
    if(pos > N) return 0;
    int& ret = dp[pos][weigh];
    if(ret != 0) return ret;
    if(n[pos].w <= weigh)
	ret = knapsack(pos+1, weigh-n[pos].w)+n[pos].v;
    ret = MAX(ret, knapsack(pos+1, weigh));
    return ret;
}

// 반복을 이용한 2번 풀이
for(int i = 1; i <= N; i++){
	for(int j = 1; j <= K; j++){
	    if(n[i].w > j) dp[i][j] = dp[i-1][j];
	    else{
		if(n[i].v+dp[i-1][j-n[i].w] > dp[i-1][j])
		    dp[i][j] = n[i].v+dp[i-1][j-n[i].w];
		else
		    dp[i][j] = dp[i-1][j];
	    }
	}
}

newdeal 4년 전 1

안녕하세요.

먼저 1번풀이인 재귀 풀이가 시간제한이 나타나는 이유는 dp배열을 0으로 초기화 했기 때문입니다. 밑과 같은 데이터에서는 답이 0이여서

방문을 했음에도 불구하고 0이라는 값을 방문 전이라고 인식하고 했던 연산을 그대로 반복하게 됩니다. 메모이제이션이 안된다는 뜻이죠.

그래서 보통 dp배열을 -1이라는 값으로 초기화를 합니다. 같은 이유로 음수가 값이 될수있는 문제라면 -1이 아닌 다른 값으로 초기화를 해야합니다.

50
0
0
0
(...)
0

yousrain 4년 전 1

가치가 0인 경우는 고려하지 않았네요 ㅠㅠ

친절하고 자세히 답변해주셔서 감사합니다!!

이해가 확실히 됐습니다. 좋은 하루 보내세요 ~~!!

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

문제

문제

출처

ICPC

배낭문제 시간초과에 대해 질문드립니다!!

yousrain 4년 전 0

newdeal 4년 전 1

yousrain 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말