aoj 動的計画法 ナップサック問題

DPL_1_C Knapsack Problem

DPL_1_C Knapsack Problem
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C

解説

ナップサック問題の各アイテムを何回でも選択できるバージョン.
ナップサックの容量を0から順に増やしていき、各容量で最大の選択を記録していく.

各容量での各アイテムの選択で価値が大きくなる方を選択する.

  1. 容量0から最大容量CAPまでのすべての各整数capについて以下を実行する

    1. すべてのアイテムitemについて以下を実行する

    2. もしitemの重さwがcapより大きい場合、何もしない

    3. cap以下の場合は、他のこれまでのitemを考慮して最大値dp[item]とitemの重さw分をcapから取り除いて代わりにitemを入れた場合の価値の大きい方でdp[item]を更新する

  2. dp[CAP]に最大容量CAPでの最大価値が格納されている

計算量

$O(N CAP)$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define MAX_N 101
#define MAX_V 1001
#define MAX_CAP 10001

struct Item { Int value, weight; };

Int N, CAP;
vector<Item> items(MAX_N, {-1, -1});
vector<Int> dp(MAX_CAP, 0);
Int v, w;

void input() {
  cin >> N >> CAP;
  loop(n,0,N) {
    cin >> v >> w;
    items[n] = { v, w };
  }
}

void solve() {
  loop(cap,1,CAP+1) {
    loop(n,0,N) {
      if (items[n].weight <= cap)
        dp[cap] = max(dp[cap-items[n].weight] + items[n].value, dp[cap]);
    }
  }
  cout << dp[CAP] << endl;
}

int main(void) {
  input();
  solve();
}