[문제풀이] 백준 12865 - 평범한 배낭

📢 문제

https://www.acmicpc.net/problem/12865

📢 알고리즘

DP(동적 계획법)

📢 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int W[101]; //i번째 물건의 무게
int V[101]; //i번째 물건의 가치
int DP[101][100001];

int main()
{
  int N, K; //물품 수, 최대 무게
  cin >> N >> K;

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

  for (int l = 1; l <= K; l++) // l은 가방무게 limit
  {
    for (int i = 1; i <= N; i++) // i번째 물건까지 고려
    {
      if (i == 1)
      {
        //담음
        if (W[i] <= l)
        {
          DP[i][l] = V[i];
        }
        else //담지 않음
        {
          DP[i][l] = 0;
        }
      }
      else
      {
        if (W[i] <= l)
        {
          // i번째 물건을 담을 수 있는 경우 : max(담는경우, 안담는 경우)
          DP[i][l] = max(DP[i - 1][l - W[i]] + V[i], DP[i - 1][l]);
        }
        else
        {
          // i번째 물건을 담을 수 없는 경우 : 이전거 그대로
          DP[i][l] = DP[i - 1][l];
        }
      }
    }
  }
  cout << DP[N][K];
}

• DP[i][l]: i번째 물건까지 고려했을 때, 가방무게 limit가 l일때의 최대 가치
• ex. DP[3][7]을 구할 때
  • 3번째 물건을 아예 담을 수 없는 경우(W[3] > l)
    • 이전거(2번째 물건까지 고려했을 때) 그대로
      = DP[2][7]
  • 3번째 물건을 담을 수 있는 경우(W[3] <= l)
    • 담는 경우 : 3번째 물건 가치 + (가방무게 limit - 3번째 물건 무게)에서의 최대 가치
      = V[3] + DP[2][l-W[3]]
    • 안 담는 경우 : 이전거 그대로
      = DP[2][7]
  • 2가지 비교 후 더 큰거
    = max(V[3] + DP[2][l-W[3]], DP[2][7])
• 중첩 for문에서 i와 l순서 바꾸면 틀림..(l이 바깥에 가도록 해야 함)
  • 이유는... 아무리 봐도 모르겠다ㅠㅠ