BOJ 12865번: 평범한 배낭

문제 설명

물건의 무게와 물건의 가치가 주어졌을 때 배낭에 넣을 수 있는 물건들의 가치합의 최대값 구하기

🔗 문제 링크

핵심 아이디어

• d[i]는 i 무게였을 때의 최대 가치
• d[j-w]는 현재 물건인 w를 넣기 전 상황
• 물건을 중복으로 넣지 않도록 역방향으로 순회하기
• 현재의 물품을 넣을지 말지를 나누어서 최대값 갱신하기

코드

#include <bits/stdc++.h>
using namespace std;
int n, k;
int d[100005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> k;
    vector<pair<int,int>> item(n);
    for(int i = 0; i < n; i++){
        cin >> item[i].first >> item[i].second;
    }
    
    
    for(int i = 0; i < n; i++){
        int w = item[i].first;
        int v = item[i].second;
        for(int j = k; j >= w; j--){
            d[j] = max(d[j], d[j - w] + v); // 안 넣기, 넣기
        }
    }
    
    cout << d[k];
}

추가 설명

• Knapsack problem 이라고도 함