12865번 평범한 배낭

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

Keywords: Knapsack, Dynamic programming

뭐…풀려고 푼건 아니고, 와이프 맥북을 빌렸 (강탈) 는데 툴체인 잘 설치됬는지 보려고 풀었다. 그래도, 적당히 해설은 남겨두어야겠지. 이 문제는 전형적인 (시실 정의 그 자체인듯) 0-1 knapsack problem 이다. 그래서, 아래와 같이 CACHE를 정의하고 점화식을 세워서 풀어주었다.

CACHE[i][w]: i 번째 물건까지 사용해서 w 무게 이하로 짐을 챙길 때 얻을 수 있는 최대 가치

CACHE[i][w] = max(CACHE[i-1][w], CACHE[i-1][w-WS[i]] + VS[i])

아래는 솔루션이다.

#include <algorithm>
#include <iostream>

using namespace std;

int N;
int K;
int WS[100];
int VS[100];
int CACHE[100][100000 + 1];

int Solve() {
  for (int w{WS[0]}; w <= K; ++w) {
    CACHE[0][w] = VS[0];
  }
  for (int i{1}; i < N; ++i) {
    for (int w{0}; w <= K; ++w) {
      CACHE[i][w] = (w - WS[i] >= 0) ? std::max(CACHE[i - 1][w - WS[i]] + VS[i],
                                                CACHE[i - 1][w])
                                     : CACHE[i - 1][w];
    }
  }
  return CACHE[N - 1][K];
}

int main(void) {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  // Read inputs.
  cin >> N >> K;
  for (auto i{0}; i < N; ++i) {
    cin >> WS[i] >> VS[i];
  }

  // Solve.
  cout << Solve() << endl;

  return 0;
}