[BaekJoon] 12865번 : 평범한 배낭

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 이 문제를 그리디라고 오해하여 중량 대비 가치가 가장 큰 경우를 넣는다고 할 경우 예외가 발생하게 됩니다.
• 그리디가 아닌 DP로 해결해야 하면 DP로 유명한 0-1 knapsack 알고리즘입니다.
• D[i][w] : 현재 w 무게가 남은 상태에서 i번째 item선택까지 최대 가치
• if w[i] < w, D[i][w] = max(D[i-1][w-w[i]]+v[i], D[i-1][w]) : i번째 Item을 담을 수 있다면, i-1번째까지 Item을 담으면서 현재 담을 수 있는 무게가 w-w[i]만큼 남은 경웅의 최대 가치합에 i번째 Item의 가치를 합한 값과 D[i-1][w] 값 비교
• else, D[i][w] = D[i-1][w]

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

int main(){
    int n,m;
    cin>>n>>m;
    
    int arr[105][100005] = {0};
    int w[105]={0};
    int v[105]={0};

    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    
    w[1] == 1?arr[1][1] = v[1] : arr[1][1] = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(w[i]<=j){
                arr[i][j] = max(arr[i-1][j-w[i]] + v[i], arr[i-1][j]);
            }else{
                arr[i][j] = arr[i-1][j];
            }
        }
    }
    cout<<arr[n][m];
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.