글 읽기 - C가 너무 클때 dp로 해결 가능한가요?

gowithmylord 7년 전 0

dp로 짜려니 무게가 1일때 부터 차례로 값을 구해나가는 점화식이 가장 일반적이어서,

10의 16승까지란 범위때문에, 너무 큰 값이 최대 무게로 들어오면 메모리초과가 뜨네요..
dp로 푸는 방법중에 이걸 해결할만한 방법이 뭐가 있죠?ㅠㅠ

#include<iostream>
#include<map>
#include<algorithm>

using namespace std;
#define max(a,b) (((a)>(b))?(a):(b))

typedef struct item{
	int w;
	int p;
}item;

typedef struct knapsack{
	map<int,int> value;
}knapsack;

bool cmp(item a, item b){
	return a.w < b.w;
}

int main(){
	int n,c;
	knapsack dp[51];
	scanf("%d",&n);
	item *data = (item*)malloc(sizeof(item)*(n+1));
	for(int i=1;i<=n;i++){
		scanf("%d %d",&data[i].w,&data[i].p);
	}
	scanf("%d",&c);
	sort(data,data+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			if( j >= data[i].w){
				dp[i].value[j] = max(dp[i-1].value[j],dp[i-1].value[j-data[i].w] + data[i].p);
			}
			else
				dp[i].value[j] = dp[i-1].value[j];
		}
	}
	printf("%d",dp[n].value[c]);
}

gowithmylord 7년 전 0

recursion을 이용하면 시간초과가 뜨네요...멘붕..

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

문제

문제

출처

ICPC

C가 너무 클때 dp로 해결 가능한가요?

gowithmylord 7년 전 0

gowithmylord 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말