[백준 12865] 평범한 배낭 (C#, C++) - soo:bak

문제 링크

12865번 - 평범한 배낭

설명

N개의 물건이 있고 각 물건은 무게와 가치를 가지며 배낭의 무게 한도 K를 넘지 않도록 물건을 선택하는 상황에서 N, K, 각 물건의 무게와 가치가 주어질 때, 가치 합의 최댓값을 구하는 문제입니다.

각 물건은 한 번만 선택할 수 있고 (0/1 배낭), N은 100 이하, K는 100,000 이하입니다.

접근법

dp[i][w]를 앞에서 i개의 물건까지 고려했을 때 무게 w 이하로 얻을 수 있는 최대 가치로 정의합니다.

i번째 물건을 담지 않으면 dp[i][w] = dp[i-1][w]이고, 담으면 dp[i][w] = dp[i-1][w-무게[i]] + 가치[i]입니다. 두 경우 중 큰 값을 선택합니다.

예를 들어 무게 한도가 7이고 물건이 3개 있을 때 (무게 6, 가치 13), (무게 4, 가치 8), (무게 3, 가치 6):

• 1번째 물건까지, 무게 7: 1번 물건 담음 → 가치 13
• 2번째 물건까지, 무게 7: 2번 물건만 담음 (무게 4, 가치 8) vs 1번 물건 담음 (무게 6, 가치 13) → 가치 13
• 3번째 물건까지, 무게 7: 기존 13 vs 2번+3번 (무게 7, 가치 14) → 가치 14

모든 i (1~N)와 w (0~K)를 채운 후 dp[N][K]가 답입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var n = int.Parse(first[0]);
      var k = int.Parse(first[1]);

      var w = new int[n + 1];
      var v = new int[n + 1];

      for (var i = 1; i <= n; i++) {
        var line = Console.ReadLine()!.Split();
        w[i] = int.Parse(line[0]);
        v[i] = int.Parse(line[1]);
      }

      var dp = new int[n + 1, k + 1];

      for (var i = 1; i <= n; i++) {
        for (var j = 0; j <= k; j++) {
          dp[i, j] = dp[i - 1, j];

          if (j >= w[i]) {
            var cand = dp[i - 1, j - w[i]] + v[i];
            if (cand > dp[i, j])
              dp[i, j] = cand;
          }
        }
      }

      Console.WriteLine(dp[n, k]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

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

  int n, k; cin >> n >> k;
  vi w(n + 1), v(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> w[i] >> v[i];

  vvi dp(n + 1, vi(k + 1, 0));

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= w[i])
        dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
    }
  }

  cout << dp[n][k] << "\n";

  return 0;
}