12865번-평범한 배낭

문제

---

제한된 무게안에 물품들을 챙겨서 가장 가치있는 배낭을 만드는 문제다

물품마다 무게와 가치가 제각각 

 

문제 해결을 위한 준비물

---

DP에 대한 지식 -  점화식을 만들어서 계산하기 위함 (...)

자세히는 모르겠지만 배낭문제(0/1 Knapsack Problem)는 동적 프로그래밍 방법(DP)로 풀어야 한다고 한다

코드

---

#include <iostream>

#define MAX_ITEM 110

using namespace std;

int N, K;
int items[MAX_ITEM];
int iWeight[MAX_ITEM];
int iValue[MAX_ITEM];
int DP[MAX_ITEM][100010] = {0};

int Max(int a, int b){ return a > b ? a : b;  }

int Solution(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= K; j++){
            if(j >= iWeight[i]) DP[i][j] = Max(DP[i-1][j], DP[i-1][j - iWeight[i]] + iValue[i]);
            else DP[i][j] = DP[i-1][j];
        }
    }

    return DP[N][K];
}

int main()
{
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> iWeight[i] >> iValue[i];
    }

    cout << Solution();

    return 0;
}

풀이

---

각 물품의 1부터 최대 무게까지 표를 만들고 자신이 적재할 수 있는 무게부터 가치를 적으면 된다 

만일 이전 물품의 가치가 자신의 무게를 제외한 배낭 무게에 있을 경우 더한다.

(이 때 자신의 무게와 이전 물품의 무게를 합쳐도 현재 무게를 넘지 않는다는 의미를 가진다  )

자신이 적재할 수 없는 무게동안은 이전 물품의 가치를 적는다 

 

이렇게 나온 표에 가장 마지막 자리가 우리가 구하고자하는 값이 나온다 

 

 

처음 써보는 동적 프로그래밍이라 아직도 이해가 되지 않는다  천천히 이해해 볼 수 밖에 없겠다