[ 백준 12865 ] 평범한 배낭 (C++)

백준의 평범한 배낭(12865) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

가방에 담을 수 있는 무게를 고려했을 때, 가방에 담긴 물건들의 최고의 가치를 구해야 하는 문제이다.

지금부터는 다음과 같은 수식을 하나 이용해서 문제를 표현해보자.

F[A][B] = C 라는 수식을 사용할 것인데, 이 수식의 의미는

A번째 물건까지 왔고 , 이 떄의 무게가 B일 때 가방에 담긴 물건들의 최고의 가치는 C입니다. 를 의미한다.

F[A][B] = C : A번째 물건까지 왔고, 가방의 무게가 B일 때 가방에 담긴 물건들의 가치는 C입니다.

# 주어진 선택지 - 1

우리는 입력으로 주어지는 첫 번째 물건부터 N번째 물건까지 순차적으로 탐색을 해 볼 것이다.

탐색을 하는 과정에서는 2가지 경우가 발생할 수 있다. 이 2가지 경우를 "고려해야할 첫 번째 부분" 이라고 표현하겠다.

1. 현재 탐색하고 있는 물건을 가방에 담을 수 있는 경우

2. 현재 탐색하고 있는 물건을 가방에 담을 수 없는 경우

먼저, 물건을 가방에 담을 수 있는 경우를 보자. 어떤 경우에 담을 수 있을까 ?? 바로, 이 물건을 가방에 담더라도 가방에 담을 수 있는 최대무게를 초과하지 않을 경우, 이 물건을 가방에 담을 수 있다.

두 번째로, 물건을 가방에 담을 수 없는 경우를 보자. 이 경우는 위에서 이야기했던 상황과 반대의 상황이다.

이 물건을 가방에 담게되면, 가방에 담을 수 있는 최대무게를 초과하게 되는 경우이다. 이 경우에는 물건을 담을 수가 없다.

# 주어진 선택지 - 2

그런데, 물건을 가방에 담을 수 있는 경우에는 또 2가지 선택권이 생기게 된다. 이 부분을 "고려해야 할 두 번째 부분" 이라고

표현하겠다.

1. 해당 물건을 가방에 담는 경우

2. 해당 물건을 가방에 담지 않는 경우

물건을 가방에 담을 수 있는 상황일 뿐, 반드시 그 물건을 가방에 담아야 하는 것은 아니다.

왜냐하면, 그 물건을 포기하고 다른 물건들을 넣음으로써 더 높은 가치를 만들어 낼 수 있는 경우가 존재할 수도 있기 때문에, 반드시 넣어야 하는 것은 아니다.

# 필요한 정보

그럼 위와 같이 고려해야할 첫 번째 부분을 통해서 물건을 가방에 넣을 수 있는지 없는지 1차적으로 판단을 한 후에, 2차적으로는 물건을 가방에 넣을 수 있다면 넣을 것인지 넣지 않을 것인지를 판단해주어야 한다.

그런데 우리가 "고려해야할 첫 번째 부분"에서 "현재 탐색하고 있는 물건을 가방에 넣을 수 있냐 없냐"를 탐색할 때에는 미리 알고있어야 할 정보가 하나 더 필요하다.

바로 "기존에 가방에 들어있는 물건들의 무게의 합" 이다. 기존의 가방의 무게를 알고 있어야, 지금 탐색하고 있는 이 물건을 넣을지 말지를 결정할 수 있다.

그럼 기존에 가방에 들어있는 물건들의 무게를 저장해 놓아야할까 ?? 만약 저장을 한다면, 그 경우의 수가 너무 많아질 수도 있다. 어떤 물건을 넣는 경우 가방의 무게, 넣지 않는 경우 가방의 무게, 그 다음 물건을 넣을 때 이전의 물건을 넣지 않고 넣었을 때의 무게, 이전의 물건을 넣고 넣었을 때의 무게... 등등... 너무 많은 경우가 존재하게 될 것이다.

그래서 본인은 가방에 넣을 수 있는 최대 무게가 K 이기 때문에 무게가 1인경우부터 K인 경우까지 모두 탐색해 주었다.

구체적인 내용은 코드를 통해서 알아보자.

for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= K; j++)
    {
        if (j >= Weight[i]) DP[i][j] = Max(DP[i - 1][j], DP[i - 1][j - Weight[i]] + Value[i]);
        else DP[i][j] = DP[i - 1][j];
    }
}

본인이 구현한 코드이다. (위의 코드에서 DP는 우리가 위에서 이야기한 F[] 수식과 같은 역할입니다.)

크게 보면 2중 for문으로 표현되어 있다.

먼저, 바깥쪽 for문(line 1)은, 물건들을 1번부터 N번 물건까지 탐색하기 위한 반복문이다.

line3은, 본인이 위에서 언급한 "가방의 무게를 1 ~ K 까지 탐색" 하기 위한 반복문이다.

즉, 위의 2개의 for문이 동작하는 방식에 의미를 부여해보자면, "i번째 물건을 통해서, 가방의 무게 j를 만들기" 라고 표현할 수 있따.

즉, line5)에 보면, 조건문이 하나 걸려있는데, 이 조건문이 위에서 언급한 1차적으로 고려해줘야 할 부분인 것이다.

"현재 물건의 무게가, 만들고자 하는 가방의 무게 보다는 크거나 같아야 가방에 넣을 수 있다" 라는 것이다.

예를 들어서 현재 물건의 무게가 5인데, 내가 만들고자 하는 가방의 무게는 1이라고 가정해보자. 가능할까 ??

가능하지가 않다. 즉, 이 경우에는 "해당 물건을 가방에 넣을 수 없다." 라는 판단이 나오게 되는 것이다.

그런데, 현재 물건의 무게가 5인데, 내가 만들고자 하는 가방의 무게가 10이라고 가정해보자. 가능할까 ??

당연히 가능하다. 어떻게 ?? 현재 물건을 통해서 가방의 무게가 5만큼 추가되기 때문에, 기존에 탐색했었던 물건들을 통해서 만들었던 무게가 5인 상황에다가 이 물건을 추가해버리면 되는 것이다.

그런데 ! 두 번째로 고려해야할 상황처럼, 반드시 그 물건을 넣어줄 필요는 없다.

따라서, line5에 조건문에 해당하는 내용을 보면, 2가지 경우 중 최적의 선택을 하게 된다.

바로, DP[i - 1][j] 와, DP[i - 1][j - Weight[i]] + Value[i] 중 더 큰 값을 선택하게 되는데, 이 수식들의 의미를 적어보면

DP[i - 1][j] 는 "기존에 탐색했던 물건들로만 무게 j를 만드는 경우" 를 의미하고

DP[i - 1][j - Weight[i]] 는 "기존에 탐색했떤 물건들로만 무게 j - Weight[i] 를 만들고, 현재 물건을 가방에 넣는 경우" 를 의미하게 된다. 즉 ! 현재 물건을 넣을지 안넣을지에 대해서 판단해주는 부분이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N, K;
int Weight[MAX];
int Value[MAX];
int DP[MAX][100010];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
    {
        cin >> Weight[i] >> Value[i];
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= K; j++)
        {
            if (j >= Weight[i])    DP[i][j] = Max(DP[i - 1][j], DP[i - 1][j - Weight[i]] + Value[i]);
            else DP[i][j] = DP[i - 1][j];
        }
    }
    cout << DP[N][K] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}