글 읽기 - c++ BFS 메모리초과문제

bearsff 2년 전 0

안녕하세요 아무리 혼자서 풀어보려고 해도 해결이 되지 않아 이렇게 질문드립니다

우선 전 무게에 따라 정렬을 한 후 가능한 모든 경우의 수를 (이 때 무게순으로 정렬 돼 있으므로 들 수 있는 무게보다 더 무거운 것은 안 들도록) 큐를 이용하여 BFS문제 풀 듯이 풀었습니다.

질문게시판에 있는 모든 반례들도 통과하는데 제출하면 9%즘에서 메모리초과가 뜹니다 ㅠㅠㅠ 무엇이 문제일까요?

도움 부탁드립니다...

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

struct bag {//loaded weight, loaded value, last loaded item's index
	int load, val, index;
};
vector<pair<int, int>> arr; // weight, value
bool compareW(pair<int, int>& a, pair<int, int>& b) {
	return a.first < b.first;
}

int bagpack(int N, int K) {
	int max_val = 0;
	queue <bag> q;
	q.push({ 0, 0, -1 });
	while (!q.empty()) {
		bag& ret = q.front();
		for (int i = ret.index + 1; i < N; i++) {
			if (ret.load + arr[i].first <= K) {
				if (i == (N - 1) || ret.load + arr[i].first + arr[i + 1].first > K)
					max_val = max(max_val, ret.val + arr[i].second);
				else
					q.push({ ret.load + arr[i].first, ret.val + arr[i].second, i });
			}
			else
				break;
		}
		q.pop();
	}
	return max_val;
}

int main(void) {
	int N, K, w, v;
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &w, &v);
		arr.push_back({ w, v });
	}
	arr.push_back({ 100001,0 });
	sort(arr.begin(), arr.end(), compareW);
	printf("%d", bagpack(N, K));
	return 0;
}

djm03178 2년 전 0

가능한 모든 경우의 수는 최악의 경우 100개의 물건을 모두 각각 넣어도 되고 안 넣어도 되는 경우이므로 최대 2^100 가지가 나옵니다. 이는 전세계의 서버를 모두 모으더라도 감당할 수 없는 메모리 양을 요구할 수준입니다.

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

문제

문제

출처

ICPC

c++ BFS 메모리초과문제

bearsff 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말