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

출처 : https://www.acmicpc.net/problem/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)가 주어진다.

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

풀이

DP에서 유명한 0-1 Knapsack Problem이다. 효율성과 게임(스타,롤)등으로 단련된 우리 건장한 꼬레아들은 무게당 가치를 따져서 최대 효용을 뽑아내려고 하겠지만, 현실에서는 부술 수 없는 물건이 더 많다.(200만원짜리 컴퓨터가 있다면, 내부 부품을 다 분해해서 들고 갈 수 있겠지만, 일반인이 50만원CPU 자체를 분해해서 들고 갈 순 없다.)

그러므로, 우린 가져갈 수 있는 범위 내에서 최대 가치를 뽑아내는 친구만을 가져가야한다. 이러한 쌍을 찾는게 0-1 knapsack Problem이다.

위 문제도 K무게 안에서 가져갈 수 있는 물건들 가치의 최댓값을 출력하는 문제이다.
어떻게 찾을 수 있을까? 단순하게 생각하면, 할 수 있는 조합을 다 해보면 된다.
nC1 + nC2+ nC3 + nC4 ....nCn까지 모든 조합을 다 해보면 된다. 들고 간다/들고가지 않는다 2가지 경우가 있으니까 , 모든 경우의 수는 2^n이다. O(2^n) n이 작다면 할만한 풀이이다.

하지만 안타깝게도 n<=100이므로, 2^100을 할 순 없으니 다른 방법을 생각해야한다.

1번을 가져간다 혹은 가져가지 않는다 -> 2번을 가져간다 혹은 가져가지 않는다 ->...
특정 문제에 대한 답을 다음 문제에 또 이용을 하는 chain이 형성되어있고, n이 완탐으로 풀기에 꽤 크면 DP를 생각할 수 있다.

DP로 문제를 접근하겠다는 건, 점화식(문제의 관계)와 초기값을 설정해주겠다는 말이랑 똑같다.

DP의 핵심은 "MainProblem을 subproblem으로 나누어서 풀어가는 겁니다."라고 이야기 합니다. Table을 이용하거나, 뭔가를 기억하거나 하는 것은 최적화를 위한 구체적인 방법일 뿐입니다. 그리고, SubProblem과 MainProblem의 관계가 점화식으로 도출될 뿐입니다.

문제 정의하기

i개를 선택했을 때, 우리는 그 전의 물품을 선택했는지, 안했는지 고려해야한다.
따라서, i개를 row로 생각하고, 최대무게 J까지의 최대가치를 알아보는 표를 작성한다고 생각하자.

P[i] = 가격(가치)을 저장한 배열
W[i] = 무게를 저장한 배열

DP[i][j] = i개를 배낭에 넣었을 때, 최대 j무게까지 얻을 수 있는 최대가치

생각해보면, 물품을 넣냐/안넣냐 2가지 밖에 없다. 따라서, DP[i][j]를 생각할 때, 이전에 있던 무게를 그대로 사용하느냐,아니면 내가 새롭게 넣느냐를 따져주면 된다. 물론, 공간이 충분해야 가방에 넣을 수 있기 때문에 그것도 함께 고려해주어야한다. 이걸 수학적인 관계식으로 나타내면 아래와 같게 된다.

DP[i][j] = max(DP[i-1][j],DP[i-1]j-W[i]]+P[i])
(단, j-w[i] >=0 즉,최대무게를 넘기지 않았을 때 이야기이다)
DP[i][j] = DP[i-1][j] (단, j-w[i]<0)

코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, K;
int P[101];
int W[101];

int DP[101][100001];

int main()
{
  cin >> N >> K;
  for (int i = 1; i <= N; i++)
  {
    cin >> W[i] >> P[i];
  }
  for (int i = 1; i <= N; i++)
  {
    for (int w = 1; w <= K; w++)
    {
      if (w - W[i] >= 0)
        DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - W[i]] + P[i]);
      else
        DP[i][w] = DP[i - 1][w];
    }
  }
  cout << DP[N][K] << '\n';
  return 0;
}

어떤 배낭을 선택했는지 알고 싶다면, DP[i][j]에서 DP[i-1][j]가 같은지 확인해보고, 같다면 해당 배낭을 선택하지 않은거다. 같지않다면 해당 배낭을 선택한 것이다.