백준 12865 - 평범한 배낭 (C++)

 

안녕하세요 besforyou입니다

 

 

---

문제 풀이

 

dp 알고리즘으로 해결해야하는 문제입니다. 그러니 2차원 배열을 하나 선언합시다.

 

int dp[101][100001];

 

여기서 dp[a][b] = v 가 의미하는것은 a번째 물건까지 참조했고, 현재 가방에 담긴 물건들의 무게는 b일때 최대 가치가 v 라는 의미입니다.

 

이를 이용해서 문제를 해결해야합니다.

 

---

 

선형 순차 탐색으로 물건을 하나하나씩 참조해가며 담을 수 있는 최대 가치를 찾을것인데, 고려해야할점이 있습니다.

 

첫번째로, 물건을 담을 수 있느냐 없느냐 입니다. 현재 참조하는 물건의 무게 + 가방에 담긴 무게가 K를 넘어버리면 담을 수 없겠죠?

 

두번째로, 가방에 물건을 담는것이 유리한가, 유리하지 않는가 입니다. 현재 참조하는 물건을 가방에 담을 수 있는데 꼭 현재 참조하는 물건을 담는다고 해서 최대 가치를 얻을 수 있는것은 아닙니다.

 

위 두 조건을 고려하면서 순차적으로 물건을 하나하나씩 참조해야합니다. 

 

여기서 첫번째 조건을 쉽게 만족시키면서 순차 검색을 하는 방법은 j = 1부터 j <= K일때까지 검색을 해보는것입니다.

 

코드

 

 

#include <iostream>
 
using namespace std;
 
int N, K;
 
int weight[101];
int value[101];
int dp[101][100001];
 
int bigger(int a, int b) {
    if ( a > b )
        return a;
    else
        return b;
}
 
int main (void) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K;
 
    for ( int i = 1 ; i <= N ; i++)
        cin >> weight[i] >> value[i];
   
    for ( int i = 1 ; i <= N ; i++ )
    {
        for (int j = 1; j <= K ; j++ )
        {
            if (j >= weight[i]) 
                dp[i][j] = bigger(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
 
    cout << dp[N][K];
 
    return 0;
}