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

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

문제 설명 및 입력과 출력 예시

 

 분명 알고 있는 알고리즘이고 금방 구현할 것이라고 생각했는데,, 최근에 일차원 DP 배열 문제들만 풀다 보니 DP 2차원 배열을 생각하지 못한 것이 패착이었다. 결국 시간을 질질 끌고 풀었다..

 

 2차원 배열에 각각 행과 열을, 가방에 담을 수 있는 최대 무게와 1~i 번째 물건까지 고려한 경우를 나타내게 설정한다.

 

 생각해보면 다음의 알고리즘이 성립한다.

•  i번째 물건의 무게가 현재의 리미트 무게보다 큰 경우
  • 당연히 담을 수 없으니 패스한다.
• 작은 경우
  • 그 물건을 넣는 경우
    • 현재 가방의 최대 무게가 limit라면, limit-그물건의무게 에서의 값 + 그 물건의 Value 값이 배열의 값이 될 것이다.
  • 그 물건을 넣지 않는 경우
    • 현재 가방의 최대 무게가 limit인 상황에서 i-1번째 물건까지 고려한 배열의 값을 집어넣어준다.
  • 요 위 두개의 값들의 max 값이 그 배열의 값이 될 것이다!

 

 아래 코드를 보면서 생각해보도록 하자.

#include <iostream>
#include <algorithm>

using namespace std;

int item, weight;
int howmany, bag;
int dp[101][100001];
int W[101];
int V[101];
void solve() {
    for (int i = 1; i <= bag; i++)
    {
        for (int j = 1; j <= howmany; j++)
        {
            if(W[j]>i){
                dp[j][i] = dp[j-1][i];
            }
            else{
                dp[j][i] = max(dp[j-1][i-W[j]] + V[j], dp[j-1][i]);
            }
        }
        
    }
    cout << dp[howmany][bag];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> howmany >> bag;
    for (int i = 1; i <= howmany; i++)
    {
        cin >> W[i] >> V[i];
    }

    for(int r=0; r<=howmany; r++)
    {
        dp[r][0] = 0;
    }
    for(int c = 0; c<=bag; c++){
        dp[0][c] = 0;
    }
    
    solve();
    return 0;
}