[백준 12865] 평범한 배낭

평범한 배낭

문제설명

가방의 최대 수용량을 넘지 않는 범위 내에서 가장 가치가 높은 물건을 가져올 때, 최대 가치를 구하자

알고리즘

1. 값을 각각 입력 받는다.
2. 이중 반복문을 사용하는데, 바깥은 가방의 정보를 저장한 index, 안쪽은 무게 K까지 돈다.
3. i번째 가방의 무게를 조회하고 현재 가방의 무게를 넘으면 이전 값, 그렇지 않으면 max함수로 비교하여 dp그래프를 채운다.
4. 배열의 가장 마지막 값을 출력한다.

---

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100001
#define MAXN 101
int N, K;
int dp[MAXN][MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    vector <pair<int, int>> bag(N+1);
    bag[0] = { 0,0 };
    for (int i = 1; i <= N; i++)//가방 무게와 가치 입력받기
    {
        int W, V;
        cin >> W >> V;
        bag[i] = { W,V };
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j<= K; j++)
        {
            if (bag[i].first <= j)//현재 배낭의 무게가 최대 수용량을 넘지 않는 경우
                dp[i][j] = max(bag[i].second+dp[i-1][j- bag[i].first],dp[i-1][j]);//새로운 물건을 넣고 가치를 구하고 , 넣기전의 가치 비교
            else
                dp[i][j] = dp[i - 1][j];//수용량을 넘었으므로 이전값으로 설정 
        }
    }


    cout << dp[N][K];//결과값 출력
    return 0;
}

고찰

이번 문제는 dp문제로 유명한 배낭 문제이다.
정리를 보고 다시 기억을 떠올려서 짤 수 있었다.

정리

1. 현재 물건의 무게가 가방의 수용 무게를 넘는 경우
   • 이전의 가치 값을 가져온다.
2. 현재 물건의 무게가 가방의 수용 무게를 넘지 않거나 같은 경우
   • 현재 물건을 넣지 않고 계산한 가치(dp[i-1][w])
   • 현재 물건을 넣고 계산한 가치 (Vi+dp[i-1][w- Wi])