백준, 12865 번(평범한 배낭)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

결과

처음에는 이 문제를 재귀(Recursion)를 이용하여 풀려고 하였다. 문제에 대한 접근 방법은 다음과 같았다.

만약 정해진 무게 내에서 최대의 가치를 가지는 상태라면 가방 안은 더 이상 물건을 넣지 못하는 상태일 것이다.
주어진 물건들을 사용자는 가방에 넣을 지 말지를 결정한다.
만약 더 이상 가방에 물건을 넣지 못하게 되면 지금까지 가방에 넣은 물건들의 가치를 합하여 하나의 경우로 본다.
모든 경우의 수를 구한 후 이를 정렬하여 최댓값을 구한다.

다음은 내가 처음 짰던 코드이다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

int N, K; // N = stuff number, K = weight

struct Object {
	int weight;
	int value;
    
	Object(int weight, int value) : weight(weight), value(value) {}

	Object operator+=(Object obj) {
		return Object(weight+obj.weight, value+obj.value);
	}

	Object operator-=(Object obj) {
		return Object(weight - obj.weight, value - obj.value);
	}

	bool operator==(Object obj) {
		return weight == obj.weight && value == obj.value;
	}

	bool operator!=(Object obj) {
		return weight != obj.weight && value == obj.value;
	}

bool compare(Object obj1, Object obj2) {
	return obj1.weight > obj2.weight;
}
 
Object whetherAbleToInsert(const std::vector<Object>& objects, int index, Object prevState) {
	return ((prevState.weight + objects[index].weight) > K) ? prevState : 
		Object(prevState.weight + objects[index].weight, prevState.value + objects[index].value);
}

std::vector<int> valCase;

//objects should be sorted before getting cases
void getValCase(const std::vector<Object>& objects, int index, Object prevState) {
	if (index > objects.size()-1) {
		return;
	}
	else if (prevState.weight + objects[objects.size()-1].weight > K) {
		valCase.push_back(prevState.value);
	}
	else if (index == objects.size()-1) {
		Object inserted = whetherAbleToInsert(objects, index, prevState);
		if (inserted == prevState) {
			valCase.push_back(prevState.value);
		}
		else {
			valCase.push_back(inserted.value);
			valCase.push_back(prevState.value);
		}
	}
	else {
		Object inserted = whetherAbleToInsert(objects, index, prevState);
		if(inserted == prevState) {
			getValCase(objects, index+1, prevState);
		}
		else {
			getValCase(objects, index+1, prevState);
			getValCase(objects, index+1, inserted);
		}
	}

std::vector<int> valueCase;
Object ifYouChose(std::vector<Object> objs, int index, Object prevObj) {
	Object nowObj(prevObj.value, prevObj.weight);

	if (index > K - 1) {
		valueCase.push_back(nowObj.value);
		return nowObj;
	}

	nowObj.value += objs[index].value;
	nowObj.weight += objs[index].weight;

	if (nowObj.weight > K) {
		nowObj.value -= objs[index].value;
		nowObj.weight -= objs[index].weight;
		valueCase.push_back(nowObj.value);
		return nowObj;
	}
	else {
		if (index == objs.size()-1) {
			valueCase.push_back(nowObj.value);
			return nowObj;
		}
		else {
			for (int i = index + 1; i < objs.size(); i++) {
				if (i == objs.size() - 1) {
					nowObj.value += objs[i].value;
					nowObj.weight += objs[i].weight;
					if (nowObj.weight > K) {
						nowObj.value -= objs[i].value;
						nowObj.weight -= objs[i].weight;
					}
				}
				else {
					Object toPlus = ifYouChose(objs, i + 1, nowObj);
					nowObj.value += toPlus.value;
					nowObj.weight += toPlus.weight;
					if (nowObj.weight > K) {
						nowObj.value -= toPlus.value;
						nowObj.weight -= toPlus.weight;
						valueCase.push_back(nowObj.value);
					}
				}
			}
		}
	}

	valueCase.push_back(nowObj.value);
	return nowObj;
}

int main() {
	std::vector<Object> objects;
	std::string input;
	std::stringstream ss;

	std::getline(std::cin, input);

	ss << input;
	input.clear();
	ss >> N >> K;
	ss.clear();

	int weight, value;
	for (int i = 0; i < N; i++) {
		std::getline(std::cin, input);
		ss << input;
		input.clear();
		ss >> weight >> value;
		ss.clear();
		objects.push_back(Object(weight, value));
	}

	std::sort(objects.begin(), objects.end(), compare);
	getValCase(objects, 0, {0,0});
	std::sort(valCase.begin(), valCase.end());

	std::cout << valCase.back();
	return 0;
}

이 방식으로 문제를 푸니, 제대로 정답은 구해졌지만 메모리 초과 메세지가 떴다. 아무래도 재귀함수의 경우 주어진 물건들의 종류가 다양해질 수록 잡아먹는 메모리가 커지다보니 이러한 결과가 나온 것 같았다. 최대한 재귀함수가 메모리를 덜 잡아먹는 방향으로 함수를 수정하였지만 계속 메모리 초과 메세지가 떴다. 적어도 이 방식이 문제에서 바란 해결 방안은 아닌 것 같았다.

인터넷에 찾아보니 이게 0-1 Knapsack 문제로 유명한 문제라는 것을 알 수 있었다. 그리고 재귀적인 방법이 아닌 동적 프로그래밍(Dynamic Programming)을 이용하면 보다 빠르게 문제를 해결할 수 있다는 것을 알 수 있었다.

동적 프로그래밍의 요지는 결국 큰 문제를 작은 문제로 나눌 수 있는 상황에서, 작은 문제의 정답들을 조합하여 큰 문제의 정답을 구하는 것이다. 언뜻 보면 재귀와 유사해보인다. 재귀 역시 커다란 문제가 작은 문제들의 반복된 조합으로 이루어져 있다. 다만 기억을 하냐 안 하냐의 차이에 있어서 그 차이가 있다. 동적 프로그래밍에서는 작은 부분에 대한 답을 저장하고 이를 활용함으로써 중복을 피한다는 점에서 단순히 연쇄적으로 답을 구하는 재귀와는 차이가 있다.

재귀의 가장 큰 문제점이 여기서 들어난다. 재귀함수는 정답을 기억하지 않는다. 예를 들어 내가 짰던 프로그램을 예로 들자면 최악의 상황을 가정하였을 때(무게는 0인데 가치가 다 다른 물건) 물건이 1개 늘어날 때마다 경우의 수가 2 배씩 늘어난다. 물건이 20가지만 되어도 백 만이 넘어가는 가짓 수가 나올 수도 있다.

너무 문제를 푸느라 힘이 빠지기도 하고 그냥 이해하는 선에서 넘어갈려고 한다.

//출처 : https://cocoon1787.tistory.com/206
#include<iostream>
#include<algorithm>
using namespace std;

int N, K;
int DP[101][100001];
int W[101];
int V[101];

int main()
{
	cin >> N >> K;

	for (int i = 1; i <= N; i++)
		cin >> W[i] >> V[i];

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= K; j++)
		{
			 
			 if (j - W[i] >= 0) DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
			 else DP[i][j] = DP[i - 1][j];
		}
	}

	cout << DP[N][K];

}

문제를 푸는 방법은 정해진 가방에서 물건을 넣는 것이 아닌 가방의 용량이 늘어감에 따라 차근차근 그 때 들어갈 수 있는 최대 가치를 구하는 것이다. 만약 비어있는 가방의 용량이 물건을 넣기에 충분하다면 선택을 해야한다. 원래의 최대 가치 상태를 유지할 것인지 아니면 강제로 라도 공간을 만들고 유지하는 것이 좋은 지 말이다. 이 때 저장하고 있는 부분은 해당 물건을 포함하지 않은 최대 가치의 상태와 강제로 공간을 마련했을 때의 가치 상태이다. 해결책에서 재귀의 냄새가 나는 데 그렇기에 연속적으로 참조가 많이 이루어질 것 같으니 이를 저장하고 이용하자는 것이 이번 문제의 요지이다. 표를 채워 나가보면 결과적으로 DP[N][K]에는 해당 무게에서의 최대 가치가 저장된다.

코딩 테스트 문제를 풀면서 느낀 점은 내가 한참 멀었다는 것!! 한 번 알고리즘에 대한 복습은 필요한 것 같다. 남의 짠 코드와 내가 짠 코드를 비교하니 정제된 코드를 짜고 싶다는 마음이 강해진다. 화이팅하자...!!

https://www.acmicpc.net/problem/12865

'뭐라도 공부해보자!!( 이론 ) > 자료구조 및 알고리즘' 카테고리의 다른 글

그래프(Graph), 넓이 우선 탐색(BFS), 깊이 우선 탐색(DFS) (0)	2022.09.17
백준 10830, 행렬 제곱 (0)	2022.09.13
분할 정복과 거듭 제곱 알고리즘 (2)	2022.09.13
백준 11401, 이항 계수 3 (0)	2022.09.07
백준 1655 번, 가운데를 말해요 (0)	2022.09.06

이것저것올리는개발일기

백준, 12865 번(평범한 배낭)

문제

입력

출력

결과

'뭐라도 공부해보자!!( 이론 ) > 자료구조 및 알고리즘' 카테고리의 다른 글

티스토리툴바

백준, 12865 번(평범한 배낭)

문제

입력

출력

결과

'뭐라도 공부해보자!!( 이론 ) > 자료구조 및 알고리즘' 카테고리의 다른 글

'뭐라도 공부해보자!!( 이론 )/자료구조 및 알고리즘' Related Articles

티스토리툴바