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

문제 링크

12920번 - 평범한 배낭 2

설명

같은 종류의 물건이 여러 개씩 있을 때, 배낭 용량을 초과하지 않으면서 만족도의 합을 최대로 하는 문제입니다.

접근법

같은 물건이 k개 있을 때 하나씩 k번 처리하면 너무 오래 걸립니다. 대신 1개, 2개, 4개, … 씩 묶어서 몇 개의 덩어리로 만들면 훨씬 빠릅니다.

예를 들어 물건이 13개 있으면 1개짜리, 2개짜리, 4개짜리, 6개짜리 네 덩어리로 나눕니다. 이 덩어리들을 적절히 골라 담으면 0개부터 13개까지 원하는 개수를 만들 수 있습니다. 13번 대신 4번만 처리하면 되는 셈입니다.

각 덩어리는 별개의 물건처럼 다룹니다. 덩어리의 무게와 만족도는 원래 값에 덩어리 개수를 곱한 것입니다.

이후 0/1 배낭 문제를 풉니다. 용량이 큰 쪽에서 작은 쪽으로 훑으면서 현재 덩어리를 넣었을 때와 넣지 않았을 때 중 더 나은 값을 고릅니다. 역순으로 훑어야 같은 덩어리를 중복해서 넣는 실수를 막을 수 있습니다.

모든 물건을 처리한 뒤 최댓값을 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var first = Console.ReadLine()!.Split();
    var n = int.Parse(first[0]);
    var m = int.Parse(first[1]);
    var dp = new int[m + 1];

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

      var cnt = 1;
      while (k > 0) {
        var take = Math.Min(cnt, k);
        var tw = w * take;
        var tv = v * take;
        for (var cap = m; cap >= tw; cap--)
          dp[cap] = Math.Max(dp[cap], dp[cap - tw] + tv);
        k -= take;
        cnt <<= 1;
      }
    }

    var ans = 0;
    for (var i = 0; i <= m; i++) if (dp[i] > ans) ans = dp[i];
    Console.WriteLine(ans);
  }
}

C++

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

typedef vector<int> vi;

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

  int n, m; cin >> n >> m;
  vi dp(m + 1, 0);
  for (int i = 0; i < n; i++) {
    int w, v, k; cin >> w >> v >> k;
    int cnt = 1;
    while (k > 0) {
      int take = min(cnt, k);
      int tw = w * take;
      int tv = v * take;
      for (int cap = m; cap >= tw; cap--)
        dp[cap] = max(dp[cap], dp[cap - tw] + tv);
      k -= take;
      cnt <<= 1;
    }
  }

  int ans = *max_element(dp.begin(), dp.end());
  cout << ans << "\n";

  return 0;
}