글 읽기 - 재귀 호출에 관한 질문

p_ce1052 1년 전 0

이 알고리즘이 맞고 틀리고를 떠나서 코드가 돌아가지 않아 질문 올립니다. dp(n-1)을 실행하면 dp배열에 0번째부터 n-1번째가 전부 계산되있어야 하는데 자기 배열만 계산되어 있습니다. 어떤 경우든 간에 0번째를 제외하면 자기 아래 함수들을 for문에서 호출하게 되있는데 왜 계산이 안되어있을까요? dp(n-1)을 실행한 후에도 하위 배열이 초기값 -1로 여전히 남아있습니다.

#include<stdio.h>
int weight[100]; //각 물건의 무게 
int value[100]; //각 물건의 가치 
int dpmaxvalue[100]; //각 물건을 마지막으로 포함했을 때의 최대가치 
int extraweight[100]; //각 물건을 포함했을 때 남은 여유무게 
int n,limit,maxvalue; //물건 개수, 최대 무게, 최대 가치 

int dp(int k){ //k번째 데이터에 대해 처리해라.
	int i,index=-1;
	int temp;
	int max=0;
	if(dpmaxvalue[k]!=-1) return dpmaxvalue[k]; //처리가 되있다면 그냥 배열 값 반환 
	//처리가 안된 경우 처리 후 반환 
	if(k==0){
		dpmaxvalue[0]=weight[0]>limit?0:value[0];
		extraweight[0]=weight[0]>limit?limit:(limit-weight[0]);
	}
	else{
		if(weight[k]>limit){ //k번째 물건을 넣을 수 없을 때 
			for(i=0; i<=k-1; i++) if(dp(i)>max){
				max=dp(i);
				index=i;
			}
			dpmaxvalue[k]=max;
			extraweight[k]=extraweight[index];
		}
		else{ //k번째 물건을 넣을 수 있을 때 
			dpmaxvalue[k]=value[k];
			extraweight[k]=limit-weight[k];
			for(i=0; i<=k-1; i++){
				if(extraweight[i]>=weight[k] && dp(i)>max){ //이전까지의 케이스에서 넣을 수 있는 곳이 있나 본다. 
					max=dp(i);
					index=i; 
				}
			}
			if(index!=-1){ //다른 곳에 들어갈 수 있는 경우를 찾았다면 
				dpmaxvalue[k]=value[k]+max;
				extraweight[k]=extraweight[index]-weight[k];
			}
		}
	} 
	return dpmaxvalue[k];
}

int main(){
	int i;
	scanf("%d%d",&n,&limit);
	for(i=0; i<n; i++) scanf("%d%d",weight+i,value+i);
	for(i=0; i<n; i++) dpmaxvalue[i]=-1;
	dp(n-1);
	for(i=0; i<n; i++) if(dpmaxvalue[i]>maxvalue) maxvalue=dpmaxvalue[i]; 
	printf("%d\n",maxvalue);
	for(i=0; i<n; i++) printf("%d ",dpmaxvalue[i]);
//	printf("\n");
//	for(i=0; i<n; i++) printf("%d ",extraweight[i]);
	return 0;
}

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

문제

문제

출처

ICPC

재귀 호출에 관한 질문

p_ce1052 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말