[BOJ] 평범한 배낭(12865)

[백준(BOJ)] 평범한 배낭(12865) C++

문제 : BOJ_12865번 평범한 배낭

문제 설명

DP(냅색 알고리즘)

DP 문제 중 유명한 문제인 평범한 배낭 문제입니다.

물품의 수와 배낭에 담을 수 있는 최대 무게가 주어집니다.

이어서 각각 물품의 무게와 가치가 주어지며, 가방 안에 최대 무게를 초과하지 않게 넣었을 때 최대 가치를 출력하는 문제입니다.

이때 주의할 것은 각각의 물품은 하나만 들어갈 수 있으므로, 하나의 물품이 중복되게 들어가는 경우의 수는 피해야 합니다.

---

Solution

dp를 이용한 풀이를 해봤습니다.

2차원 dp를 다음과 같이 만들었습니다.

dp[i 번째까지 물건을 사용했을 때][무게가 j 일 때] = 최댓값

1~n까지의 물건에서 현재 최댓값을 알고자 하는 무게가 j라고 했을 때, 1~n 번의 물건을 사용하여 j의 무게에서 가치의 최댓값을 갱신해 주는 dp 식입니다.

2중 for 문의 첫 번째 for 문에서 1~n까지의 물건을 순회하며, 두 번째 포문에서 배낭의 최대 무게를 순회하며 dp 값을 갱신해 줍니다.

이때 처음 dp[i][j]의 값은 i 번째 물건을 j 무게에서 담지 않은 경우, 즉 dp[i-1][j]로 초기화해주고 값을 비교해 주어야 합니다.

비교해 줘야 하는 값은 dp[i][j-i 번째 물건의 무게] + i 번째 물건의 가치와 비교해 줘야 합니다.

이 값은 i 번째 물건을 현재 무게에 담았을 때의 최대 가치임을 알 수 있습니다.

즉 현재 i 번째의 물건을 j 무게에서 담았을 때와 담지 않은 경우를 비교하며 dp를 갱신해 줍니다.

---

Description

• 물건의 무게와 가치는 pair<int,int>로 담아주었습니다.

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> adj;
int dp[101][100001];
int n, k;
int main(){
    cin >> n >> k;
    adj.resize(n+1);
    for(int i=1;i<=n;i++){
        int w,v;
        cin >> w >> v;
        adj[i]={w,v};
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=dp[i-1][j];
            if(j-adj[i].first>=0){
                int value = dp[i-1][j-adj[i].first]+adj[i].second;
                dp[i][j]=max(dp[i][j],value);
            }
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}