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

문제

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

12865번: 평범한 배낭

 

풀이 과정

 

이 문제는 다이나믹 프로그래밍하면 가장 대표적인 가방에 무게와 가치가 있는 물건을 최대 가치가 되도록 담는 문제이다. 

다이나믹 프로그래밍의 핵심이라고 한다면 이전의 계산을 통해 중복되는 계산을 피하는 것에 있다. 이는 분할 정복과 느낌이 비슷하다.

N개의 입력에 의해 발생할 수 있는 가짓수는 2^N 가지이다. DP는 이를 모두 확인하는 것 보다 효율적으로 구현하는 것이 목적이다.

 

1차원 배열의 값 dp[i]는 무게가 i 일 때 얻을 수 있는 가장 큰 가치를 의미한다.

 

가방에는 최대 K무게 만큼의 물건을 넣을 수 있다. 매번 입력마다 업데이트를 진행한다. 이때 입력되는 모든 물체의 무게를 W라고 할 때 W이상 K이하의 저장된 값들을 업데이트해야 한다.

 

그 이유를 좀 자세히 예를 들어 설명하자면, 만약 최대 용량이 10인 가방에 무게가 7짜리 물건을 넣을 수 있을 때  1) 7을 넣어 최종 중량이 7인 경우, 2) 이미 1의 무게가 들어있었고 최종 중량이 8이 되는 경우, 3) 이미 2의 무게가 들어있어 최종 중량이 9가 되는 경우, 4) 이미 3의 무게가 들어있어 최종 중량이 10이 되는 경우가 존재한다. 즉 4가지 경우에 대해 최대 가치를 업데이트해야 한다. 이때 7짜리 무게의 가치 대신에 더 높은 가치의 조합이 존재했다면 이전의 조합에 의한 최대 가치를 유지한다. 만약 무게가 7인 물건을 넣었을 때 가치가 더 높아진다면 해당 값들이 모두 업데이트된다.

 

이를 확장한다면, 새로운 (W, V) 상태의 물건이 입력되었을 때 dp의 무게가 W이상의 상태에 대한 업데이트를 해야 한다는 의미이다.

dp [0], dp [1],... , dp [K-W-1], dp [K-W] 값들이 업데이트되는데, 이는 dp [j] = max((dp [j-W] + V), dp [j]) 를 따른다.

 

dp [i]에는 현재까지 무게가 i일 때 얻을 수 있는 최대 가치가 저장되어 있기 때문에,

(W를 뺀 무게일 때의 최대 가치와 V를 더한 값)과 (저장되어 있던 최대 가치)를 비교하여 최대 가치를 업데이트해야 한다.

 

이를 코드로 구현하게 되면 소스코드와 같다.

 

소스 코드

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


int N,K,W,V;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int dp[100001]={0};

    cin >> N >> K;
    for(int i=1;i<=N;i++){
        cin >> W >> V;
        for(int j=K; j>=W; j--){
            dp[j] = max((dp[j-W] + V), dp[j]);
        }
    }

    cout << dp[K];

    return 0;
}

 

결과 및 후기

첫 제출 때 dp를 이중 배열로 구현하여 dp [101][100001] 크기로 설정하였다. 그리고 들어간 물건의 수를 i로 가방에 든 최종 무게를 j라고 했을 때 dp [i][j]에 업데이트했었다. 하지만 구현하고 보니 가방에 물건이 몇 개가 들어갔는지는 필요하지 않았다. 최종적으로 최대 가치만 구하면 되는 문제였다. 따라서 [101]을 유지할 필요 없이 dp [100001]로도 해결이 가능했다. 메모리를 절약할 수 있는 위 소스코드와 같이 다시 구현하게 되었다.