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

[문제]

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

[문제 풀이]

냅색 문제의 대표적인 예이다. DP 공부가 부족하였기에 냅색 공부를 하기위해 동영상을 보고 참고해서 풀었다.

 

 

https://youtu.be/rhda6lR5kyQ

참고한 동영상. 설명이 친절하셔서 도움이 많이 되었습니다.

 

해당 영상에서도 나오지만 중요한건 dp[배낭의 갯수][무게]를 만들고

//cost는 해당 배낭의 무게 value는 해당 배낭의 가치이다.
dp[배낭2][무게] = max(dp[배낭2 - 1][무게], dp[배낭2 - 1][무게 - cost[배낭2]] + value[배낭2]

해당 코드를 이용해서 마지막 배낭의 최대 무게가 총 어느정도의 값어치를 가지는지 확인을 하면 된다.

[회고]

1. 굉장히 유명한데 비해서 여태까지 제대로 파고 들어본적이 없어서 처음볼때 익숙하면서도 어려웠다.

2. 처음엔 그리디 문제인줄 알고 접근했는데 아닌걸 보고 완탐인가 의심을 했다가 아무리 봐도 완탐이 아니라서 문제 유형을 보니 DP인걸 보고 영상을 보기로 결심함.

3. 문제를 풀고 나니 느끼는데 여태까지 코딩 테스트에서 해당 알고리즘을 이용한 문제가 몇가지 나왔던 것이 기억이 난다. 제대로 체득을 하고 가자.

[코드]

#include <iostream>
#include <algorithm>

using namespace std;

int dp[101][100001];
int cost[101];
int value[101];
int n,k;

int main(){
    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        cin>>cost[i]>>value[i];
    }

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=k;j++){            
            if(j - cost[i] >= 0){
                dp[i][j] = max(dp[i - 1][j - cost[i]] + value[i], dp[i - 1][j]);
            }
            else{
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout<<dp[n][k]<<endl;

    return 0;
}