[백준/BOJ] 12865번 : 평범한 배낭 (배낭 문제, Gold V)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 12865번 : '평범한 배낭' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold V에 해당하며, 문제를 풀이하기 위해 배낭 문제 알고리즘에 대한 이해가 필요합니다.

 

 

12865번 : 평범한 배낭

 

각각의 무게와 가치가를 가지고 있는 N개의 물품 중 일부를 무게 제한 K인 배낭에 넣어 얻을 수 있는 최대한의 가치를 구하는 문제입니다.

이는 배낭 문제라는 유명한 알고리즘 문제로, 각각의 물건을 순차적으로 배낭에 넣을지를 선택하면서 최적의 물품을 갱신해나가면서 동적 프로그래밍으로 풀이해야하는 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int dp[101][100001] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;
    vector<pair<int, int>> obj(N+1);
    for(int i=1; i<=N; i++)
        cin >> obj[i].first >> obj[i].second;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=K; j++) {
            dp[i][j] = dp[i-1][j];
            if(obj[i].first <= j)
                dp[i][j] = max(dp[i][j], dp[i-1][j-obj[i].first] + obj[i].second);
        }
    cout << dp[N][K];
}

 

pair로 선언된 obj의 경우, first에는 물품의 무게, second에는 물품의 가치를 저장해줍니다.

그 다음 "dp[i][j] = i번까지 물품을 무게 제한이 j인 배낭에 넣었을 때 얻을 수 있는 최대 가치 값"으로 정의되는 dp를 선언하여 값을 갱신해주면 됩니다.

 

점화식의 경우에는, dp[i][j] = max(dp[i][j], dp[i-1][j-obj[i].first] + obj[i].second) 즉 현재 배낭에서 (일부 물건을 빼거나 해서) obj[i]를 넣을 수 있을 때, obj[i]를 넣는 경우와 그렇지 않은 경우의 가치를 비교해서 max 값으로 값을 갱신해주는 것입니다.

이렇게 이중 for문으로 문제를 풀이하여 dp[N][K]를 구해주면 문제가 풀립니다.

 

 

 

제출해보면 위와 같은 기록으로 정답 처리를 받을 수 있습니다.

 

 

 

이렇게 해서 단계별로 풀어보기의 '동적 계획법 1' 단계까지 모두 풀이하였습니다.

다음 포스트부터는 '그리디 알고리즘' 문제들 중 안 푼 것을 풀이해보도록 하겠습니다.