12865번: 평범한 배낭

12865번: 평범한 배낭

사용 언어: C++

문제 요약

한 달 후 군대에 가는 준서는 여행을 떠나기 전 최대한 즐거운 추억을 만들기 위해, 배낭에 넣을 수 있는 물건의 가치 합의 최댓값을 고민하고 있다.

준서는 N개의 물건을 가지고 있고, 각 물건은 무게 W와 가치 V를 갖는다.

배낭에 넣을 수 있는 최대 무게는 K일 때, 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하라.

단, 각 물건은 한 번씩만 사용할 수 있다.

풀이

이 문제는 전형적인 0-1 배낭 문제로, 동적 계획법(DP)을 이용해 푸는 문제다.

• dp[j]: 최대 무게가 j일 때의 최대 가치
• 각 물건을 한 번씩만 사용할 수 있으므로, 무게 j부터 역순으로 갱신해야 한다.

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, K;
    cin >> N >> K;
    vector<pair<int,int>> items(N);
    
    for(int i=0; i<N; i++)
    {
        cin >> items[i].first >> items[i].second;
    }
    
    vector<int> dp(K+1, 0);
    
    for(int i=0; i<N; i++)
    {
        int w = items[i].first;
        int v = items[i].second;
        
        for(int j=K; j>=w; j--)
        {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    
    cout << dp[K] << '\n';

    return 0;
}