[백준알고리즘] 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);
}