[BOJ 12865] 평범한 배낭 - C++

문제

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

12865번: 평범한 배낭

풀이

이 문제는 대표적인 0-1 knapsack(배낭) 문제이다. 무게의 한계가 정해져 있을 때 최대의 가치를 가지도록 물건을 배낭에 넣으면 된다. 

 

• 배낭에 물건을 넣는 경우(1), 넣지 않는 경우(0)로 문제가 작게 쪼개질 수 있다. 
• 물건을 넣을 때는 무게와 가치를 모두 고려한다. 

문제에서 각각의 물건의 무게와 가치는 다음과 같다.

무게	6	4	3	5
가치	13	8	6	12

 

무게의 한계가 7이라고 했을 때, 문제를 NS("1234", 7) 이라고 정의하자.

이 문제를 (1) 4번째 물건을 넣는 경우, (2) 4번째 물건을 넣지 않는 경우로 쪼갤 수 있다. 

 

(1) NS("123", 7-4번째 물건의 무게) + 4번째 물건의 가치 = NS("123", 2) + 12

(2) NS("123", 7)

 

최대의 가치를 가져야 하므로 위 2가지의 경우 중 max 값을 NS("1234", 7)의 값으로 설정하면 된다. 

 

위 내용을 일반화하면, NS(n, w) = max(NS(n-1, w - wi) +vi, NS(n-1, w)) 로 점화식을 세울 수 있다. 

• n : 선택할 수 있는 물건의 개수
• w : 무게의 한계
• wi : i번째 물건의 무게
• vi : i번째 물건의 가치

값들을 채워갈 때 고려해야 할 것이 무게, 가치로 2가지 이므로 값을 2차원 배열 d[n][w]에 채운다. 

 

무게가 0이거나 0번째 물건은 없으므로 2차원 배열에서 아래와 같이 초기값을 채운다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0
2	0
3	0
4	0

 

1. 물건의 무게 <= 현재 무게 한계
   • d[i][j] = max(d[i-1][j-w[i]] + v[i], d[i-1][j]) 
   • 현재 무게 한도 내에 물건을 넣을 수 있으므로 넣었을 때, 넣지 않았을 때를 비교하여 최대의 가치를 선택한다.
2. 물건의 무게 > 현재 무게 한계
   • d[i][j] = d[i-1][j]
   • 현재 무게 한도 내에 물건을 넣을 수 없으므로 넣지 않았을 때의 값이 가치가 된다. 

 

위 절차에 따라 배열을 채우면 아래와 같은 결과를 얻는다.

0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

따라서 결과값은 d[물건의 개수][무게의 한계]로 얻을 수 있다. 

 

코드

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

int n, k;           // 물품 수, 버틸 수 있는 무게
int w[105], v[105]; // 각 물건의 무게, 해당 물건의 가치
int d[105][100005]; // [몇번째 물건, 무게 한도] 일때 optimal profit
/**
 * - wi <= w 일 때
 * d[i][w] = max(d[i-1][w-wi] + vi, d[i-1][w])
 * - wi > w 일 때
 * d[i][w] = d[i-1][w]
 */
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  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 (w[i] <= j)
        d[i][j] = max(d[i - 1][j - w[i]] + v[i], d[i - 1][j]);
      else
        d[i][j] = d[i - 1][j];
    }
  }


  cout << d[n][k];
}