[백준/c++] 12865 평범한 배낭

 

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

12865번: 평범한 배낭

 

🗓 knapsack

• 조합 최적화의 대표적인 문제 유형
• 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제
• 문제 유형
  • 짐을 쪼갤 수 있을 때 : 무게를 소수로 쪼갤 수 있음, 분할가능 배낭문제(Fractional Knapsack Problem), 그리디 알고리즘
  • 짐을 쪼갤 수 없을 때 : 0-1 배낭문제(0-1 Knapsack Problem), 다이나믹 프로그래밍

 

출처 : 위키 백과 https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

 

✨ 문제 풀이

 

짐을 쪼갤 수 없는 knapsack 문제 유형이므로 다이나믹 프로그래밍으로 해결해야 한다.

이 문제는 모든 물품에 대해서 무게와 비교해보면서 선택을 해야 하는 문제이다

 

1. 이 물품을 넣겠다
  (1) 안에 있는 물품을 모두 그대로 두고 넣는다
  (2) 안에 있는 물품을 빼고 넣는다
2. 이 물품을 넣지 않겠다
  (1) 물품의 무게가 가방의 최대 무게보다 무거움
  (2) 이 물품을 넣는 게 이 물품을 넣지 않는 것보다 가치가 낮음

 

다음과 같은 경우를 생각해보자

 

가방에 최대한 담을 수 있는 무게 : 5
-- 물품의 종류 --
물품 1 : 무게 4, 가치 2
물품 2 : 무게 3, 가치 4
물품 3 : 무게 1, 가치 5

 

가방에 최대한 무게 1만큼 실을 때:

 

	최대 가치
물품 1 (무게 4, 가치 2)	0
물품 2 (무게 3, 가치 4)	0
물품 3 (무게 1, 가치 5)	5

 

물품 1, 2, 3 순서대로 비교를 해보자.

물품 1 : 무게가 1보다 커서 넣을 수 없음, 최대 가치 0

물품 2 : 무게가 1보다 커서 넣을 수 없음, 최대 가치 0

물품 3 : 무게 1이므로 넣을 수 있음, 최대 가치 5

 

가방에 최대한 무게 2만큼 실을 때:

 

	최대 가치
물품 1 (무게 4, 가치 2)	0
물품 2 (무게 3, 가치 4)	0
물품 3 (무게 1, 가치 5)	5

 

물품 1, 2, 3 순서대로 비교를 해보자.

물품 1 : 무게가 2보다 커서 넣을 수 없음, 최대 가치 0

물품 2 : 무게가 2보다 커서 넣을 수 없음, 최대 가치 0

물품 3 : 무게 1이므로 2보다 작아서 넣을 수 있음, 최대 가치 5

 

 

가방에 최대한 무게 3만큼 실을 때:

 

	최대 가치
물품 1 (무게 4, 가치 2)	0
물품 2 (무게 3, 가치 4)	4
물품 3 (무게 1, 가치 5)	5

 

물품 1, 2, 3 순서대로 비교를 해보자.

물품 1 : 무게가 3보다 커서 넣을 수 없음, 최대 가치 0

물품 2 : 무게가 3과 같으므로 넣을 수 있음, 최대 가치 4

물품 3 : 무게가 1이므로 3보다 작아서 넣을 수 있음

👉 앞에 넣은 물품의 무게가 3이고 가치가 4이다!

  👉 안에 있는 물건을 빼지 않고 넣을 수 있는가?? No

  👉 안에 있는 물건을 빼고 넣을 때 현재 물품이 더 가치가 큰가? Yes

    👉 따라서 최대 가치 5

 

 

가방에 최대한 무게 4만큼 실을 때:

 

	최대 가치
물품 1 (무게 4, 가치 2)	2
물품 2 (무게 3, 가치 4)	4
물품 3 (무게 1, 가치 5)	9

 

물품 1, 2, 3 순서대로 비교를 해보자.

물품 1 : 무게가 4와 같으므로 넣을 수 있음, 최대 가치 2

물품 2 : 무게가 1이므로 4보다 작아서 넣을 수 있음

  👉 앞에 넣은 물품의 무게가 4이고 가치가 2이다!

    👉 안에 있는 물건을 빼지 않고 넣을 수 있는가?? No

    👉 안에 있는 물건을 빼고 넣을 때 현재 물품이 더 가치가 큰가? Yes

      👉 따라서 최대 가치 4

물품 3 : 무게가 1이므로 4보다 작아서 넣을 수 있음

  👉 앞에 넣은 물품의 무게가 4이고 가치가 3이다!

    👉 안에 있는 물건을 빼지 않고 넣을 수 있는가?? Yes

      👉 따라서 최대 가치 4 + 5 = 9

 

 

가방에 최대한 무게 5만큼 실을 때:

 

	최대 가치
물품 1 (무게 4, 가치 2)	2
물품 2 (무게 3, 가치 4)	4
물품 3 (무게 1, 가치 5)	9

 

물품 1, 2, 3 순서대로 비교를 해보자.

물품 1 : 무게가 1이므로 5보다 작아서 넣을 수 있음

물품 2 : 무게가 3이므로 5보다 작아서 넣을 수 있음

  👉 앞에 넣은 물품의 무게가 4이고 가치가 2이다!

    👉 안에 있는 물건을 빼지 않고 넣을 수 있는가?? No

    👉 안에 있는 물건을 빼고 넣을 때 현재 물품이 더 가치가 큰가? Yes

      👉 따라서 최대 가치 4

물품 3 : 무게가 1이므로 5보다 작아서 넣을 수 있음

  👉 앞에 넣은 물품의 무게가 4이고 가치가 3이다!

    👉 안에 있는 물건을 빼지 않고 넣을 수 있는가?? Yes

      👉 따라서 최대 가치 4 + 5 = 9

 

백준에 나와 있는 예제도 해보자

가방에 최대한 담을 수 있는 무게 : 7
-- 물품의 종류 --
물품 1 : 무게 6, 가치 13
물품 2 : 무게 4, 가치 8
물품 3 : 무게 3, 가치 6
물품 4 : 무게 5, 가치 12

 

무게에 따라 최대 가치를 구해보면 다음과 같다

이번엔 간단하게 표로 모두 쓰겠다

 

	1일 때 최대	2일 때 최대	3일 때 최대	4일 때 최대	5일 때 최대	6일 때 최대	7일 때 최대
물품 1 무게 6, 가치 13	0	0	0	0	0	13	13
물품 2 무게 4, 가치 8	0	0	0	8	8	13	13
물품 3 무게 3, 가치 6	0	0	6	8	8	13	14
물품 4 무게 5, 가치 12	0	0	6	8	12	13	14

 

 

위의 내용을 코드로 작성해보자

1. 이 물품의 무게는 가방의 최대 무게보다 크다
 (1) 담지 않는다 - 넣지 않았을 때의 최대 가치
2. 이 물품의 무게는 가방의 최대 무게보다 작다
 (1) 물품을 담는다
 	(1) 안에 있는 물품을 모두 그대로 두고 넣는다
	(2) 안에 있는 물품을 빼고 넣는다
 (2) 담지 않는다 - 최대 가치가 더 작아진다.

 

1번의 경우는 쉽게 다음과 같이 작성할 수 있다

if (j < weight)
	dp[i][j] = dp[i - 1][j];

 

 

2번의 경우는 (1)과 (2) 중에서, 즉 담지 않았을 때의 최대 가치와 담았을 때의 최대 가치를 비교해서 더 큰 값을 저장한다.

예를 들어 최대 무게가 5인 가방에 무게가 3인 물품을 넣는다고 했을 때,

이 물품이 없으면서 무게가 2일 때 (5-3)의 최대 가치 + 이 물품의 가치를 더한 값과

이 물품이 없으면서 무게가 5일 때 최대 가치 중에서 더 큰 값을 구하고 저장한다.

dp[i][j] = max(
	dp[i - 1][j],
	dp[i - 1][j - weight] + value
    );

 

총 코드는 다음과 같다

#include <iostream>
using namespace std;

int N, K, item[102][2], dp[102][100'003];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++)
    {
        cin >> item[i][0] >> item[i][1];
    }

    for (int i = 1; i <= N; i++)
    {
        int weight = item[i][0], value = item[i][1];
        for (int j = 0; j <= K; j++)
        {
            if (j < weight)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(
                    dp[i - 1][j],
                    dp[i - 1][j - weight] + value);
        }
    }

    cout << dp[N][K] << '\n';
}