[boj] 백준 12856 평범한 배낭 - 동적 프로그래밍

[문제]

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

12865번: 평범한 배낭

 

[풀이]

0/1 knapsack 문제로 잘 알려져있는 동적 프로그래밍 대표 문제이다. 물건을 쪼갤 수 있는 경우 greedy로 풀지만 0/1로 나눌 수 없다면 동적 프로그래밍으로 해결한다.

dp[i][j] 배열은 i 번째만큼의 물건을 배낭에 넣을 수 있고, j 만큼의 무게를 견딜 수 있다고 할 때 배낭에 있는 물건들의 최대 가치를 저장한다. dp의 점화식은 크게 2개로 나눠서 생각할 수 있다.

 

첫번째는 i번째 물건이 배낭이 견딜 수 있는 무게보다 적게 나가는 경우. 이는 또 2가지로 나눠진다.

1) 해당 물건을 넣지 않음. 즉, i-1 번째 물건까지를 배낭에 넣었을 때의 최적의 값

2) 해당 물건을 넣음. 즉, i-1 번째 물건까지 넣었을 때, 현재 배낭이 버틸 수 있는 최대 무게에서 i번째 물건의 무게만큼을 뺀 배낭이 견딜 수 있는 최적의 값 + 해당 물건의 가치

dp[i][j] = max(dp[i-1][j-vec[i].first] + vec[i].second, dp[i-1][j])

//vec[i].first는 i번째 물건의 무게를, vec[i].second는 i번째 물건의 가치를 의미한다.

이 중 최대값으로 갱신해준다.

 

두번째는 i번째 물건이 배낭이 견딜 수 있는 무게보다 더 많이 나가는 경우. 이는 해당 물건을 배낭에 넣을 수 없으므로 i-1 번째 물건까지를 배낭에 넣었을 때의 값이 된다.

dp[i][j] = dp[i-1][j]

 

[코드]

 

// Created by strit on 2022-03-16. gold5 12865 평범한 배낭 - dp
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace::std;

int main() {
    //배낭에 넣을 수 있는 물건들의 가치의 최대값
    int dp[101][100001] = {0, }; //i번째 물건까지, j 무게만큼의 최대 가치합
    int n, k; //물품의 수, 버틸 수 있는 무게
    cin >> n >> k;
    vector<pair<int, int>> vec;
    for(int i=0; i<n; i++){
        int w, v;
        cin >> w >> v;
        vec.push_back({w, v});
    }

    int answer = -987654321;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(vec[i-1].first <= j){
                dp[i][j] = max(dp[i-1][j-vec[i-1].first] + vec[i-1].second, dp[i-1][j]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
            answer = max(answer, dp[i][j]);
        }
    }

    cout << answer;

}