[백준알고리즘] 12865번: 평범한 배낭 -C++

[백준알고리즘] 12865번: 평범한 배낭 -C++

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

대표적인 Knapsack 알고리즘의 문제다. 조합의 문제고, 동적계획법(DP; Dynamic Programming)을 사용하는 대표적인 문제다. 아래의 두 링크는 위키피디아인데 영어가 못 알아먹겠어도 내용이 많다. 잘 정리된 블로그들도 많으니 참고하면 좋을 듯하다.

Knapsack problem - Wikipedia

Knapsack problem

배낭 문제 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

배낭 문제 - 위키백과, 우리 모두의 백과사전

 

이러한 Knapsack 문제는 두 가지 유형이 있다. 가치 있는 물건을 잘라서라도 가져갈 수 있는 Fractional Knapsack과 물건을 절대 자를 수 없는 0-1 Knapsack이다.

 

Fractional Knapsack의 경우에는 쉽다. 가장 가치가 높은 물건부터 최대한 꾹꾹 눌러 담아가면 된다. 그렇기 때문에 0-1 Knapsack이 상대적으로 DP를 공부하기에 적절하고 더 유명하다.

 

아래는 예전에 파이썬으로 풀었을 때의 블로그 글이다. 내 블로그의 첫 글이자 어쩌면 글 하나 작성하는데 가장 오래 걸렸던 문제다. 나름 HTML도 모르는데 표도 넣으려고 찾아가면서 했었다. 오늘은 이만큼 자세히는 풀지 않을 것 같다.

[백준알고리즘] 12865번: 평범한 배낭 -Python (tistory.com)

[백준알고리즘] 12865번: 평범한 배낭 -Python

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

시작한 아이디어는 간단하다. 시간제한이 2초로 넉넉한 덕분에 대략 2억 번이라는 충분하고도 남아도는 연산 횟수가 있었기 때문이다. 

생각했던 아이디어는 아래와 같다.

• 우선 무게순으로 물품들을 정렬한다.
• 가방에 기존에 들어갈 수 있던 조합에서 해당 물품을 추가했을 때의 무게와 가치를 구한다.
• 각 조합별 늘어난 총 무게에서 구할 수 있는 최대의 가치를 구한다.

 

이렇게 할 수 있었던 이유는 무게 순 정렬하는 것도 \( 100 \) 개의 item 밖에 없었고, 준서가 버틸 수 있는 무게가 \( 100,000 \) 밖에 되지 않았기 때문이다. 따라서 조합별 늘어난 무게를 각각 구하더라도 \( O(nk) \) 밖에 되지 않았고, 이는 \( 10,000,000 \) 연산 밖에 되지 않기 때문이다.

 

그래서 위의 아이디어를 반복하면서 넣을 수 있는 물건들의 조합에서 최대 가치를 구했다.

 

다만, 글 맨 아래 코드에서 knapsack 함수의 이중 for문의 안쪽 for문에서 \( i \)를 감소하면서 접근했다. \( i \)를 증가하면서 접근하면 다음과 같은 문제가 생기기 때문이다.

item weight : 1, item value : 2

i = 0
max values index : 0 1 2 3 4 5 6 ...
max values         : 0 2 0 0 0 0 0 ...

i = 1
max values index : 0 1 2 3 4 5 6 ...
max values         : 0 2 4 0 0 0 0 ...

i = 2
max values index : 0 1 2 3 4 5 6 ...
max values         : 0 2 4 6 0 0 0 ...

...

 

즉, 갱신되지 말아야 할 무게들이 갱신되는 문제가 생긴다. 무게가 1이고 가치가 2인 물품은 하나인데, 해당 물품을 여러 번 챙기는 것과 같은 것이다. 이러한 문제를 해결하기 위해서 큰 무게에서 작은 무게로 \( i \)를 감소하면서 접근했다.

 

아래는 위의 로직대로 푼 C++ 코드다. sort는 항상 헷갈리는 것 같다. vector냐 어디냐에 따라서 계속 달라지니.. vector에서 오름차순은 세 번째 인자로 std::less<>()를 넣는 것과 같다.

#include <iostream>
#include <vector>
#include <algorithm>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int knapsack(std::vector<std::pair<int, int>> pairsWeightValue, int maxWeight)
{
	std::vector<int> maxValues(maxWeight + 1, 0);

	for (auto& pairWeightValue : pairsWeightValue)
	{
		int& weight = pairWeightValue.first;
		int& value = pairWeightValue.second;

		for (int i = maxWeight - weight; i >= 0; i--)
		{
			if (0 < i && maxValues[i] == 0)
				continue;

			maxValues[i + weight] = std::max(maxValues[i] + value, maxValues[i + weight]);
		}
	}

	return *std::max_element(maxValues.begin(), maxValues.end());
}

void solve(void)
{
	int n, k;
	std::cin >> n >> k;

	std::vector<std::pair<int, int>> objects(n);
	for (auto& object : objects)
		std::cin >> object.first >> object.second;

	//std::sort(objects.begin(), objects.end(), std::less<>());
	std::sort(objects.begin(), objects.end());
	std::cout << knapsack(objects, k);
}