Zenn
🐸

[鉄則A19] Knapsack 1

2024/03/27に公開
Ruby
AtCoder
競プロ
ナップサック問題
動的計画法
tech

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_s

ナップサック問題の基礎。

問題の要約

  • ナップサックに限界まで入れたときの最大の価値は？

アイテムの w を「重さ」とするより「大きさ」とした方がイメージしやすい。

例1で問題を理解する

大きさ 7 の袋に、

アイテム 大きさ(w) 価値(v)
1 3 13
2 3 17
3 5 29
4 1 10

のアイテムの詰め込んで価値を最大にしたいとき 1 2 4 を選択すると大きさの合計はちょうど 7 で価値は 40 になる。同様に他の組み合わせを試すものの価値 40 を超えられないので答えは 40 になる。

全探索な解き方 (TLE)

N, W = gets.split.collect(&:to_i)                    # => [10, 285]
WV = N.times.collect { gets.split.collect(&:to_i) }  # => [[29, 8000], [43, 11000], [47, 10000], [51, 13000], [52, 16000], [66, 14000], [72, 25000], [79, 18000], [82, 23000], [86, 27000]]
value = 0
(1..N).each do |max|
  WV.combination(max) do |items| # max 個を選択するすべての組み合わせ
    w = items.sum { |w, v| w }   # 大きさの合計
    if w <= W                    # 袋に入りきるなら
      v = items.sum { |w, v| v } # 価値の合計の
      value = [value, v].max     # 大きいほうを残す
    end
  end
end
p value                                              # => 87000

動的計画法の検証のために全探索版も書けるようにしたい。

DPを使う上での部分和との違い

部分和 ナップサック
左上角の初期値 true 0
左上から来たとき そのままコピー 価値を足す
左上と上 存在する方ならどちらでも 値の大きい方を取る
最後の答え 右下の角 最後の行の最大値

二次元な動的計画法 (AC)

753 ms
N, W = gets.split.collect(&:to_i)                    # => [10, 285]
WV = N.times.collect { gets.split.collect(&:to_i) }  # => [[29, 8000], [43, 11000], [47, 10000], [51, 13000], [52, 16000], [66, 14000], [72, 25000], [79, 18000], [82, 23000], [86, 27000]]
WV.unshift(nil)                                      # => [nil, [29, 8000], [43, 11000], [47, 10000], [51, 13000], [52, 16000], [66, 14000], [72, 25000], [79, 18000], [82, 23000], [86, 27000]]
dp = Array.new(N.next) { Array.new(W.next) }
dp[0][0] = 0
(1..N).each do |y|                  # 縦軸: 1..アイテム数
  (0..W).each do |x|                # 横軸: 0..容量
    w, v = WV[y]                    # w:大きさ v:価値
    if x < w
      # y 番目のアイテムが使えない
      dp[y][x] = dp[y - 1][x]
    else
      # y 番目のアイテムを使えるが、使わない or 使う
      # 左上から来た場合のみ「使う」ので WV[y] の価値を足して埋める
      a = dp[y - 1][x - w]        # 左上
      b = dp[y - 1][x]            # 上
      case
      when a && b                 # 左上と上がある場合
        dp[y][x] = [a + v, b].max # 大きい方をとる
      when a                      # 左上だけある場合
        dp[y][x] = a + v          # 価値を足したのを埋める
      when b                      # 上がある場合
        dp[y][x] = b              # 単に下にずらす
      end
    end
  end
end
p dp[N].max_by { |e| e || 0 }                        # => 87000

nil との演算を避けるためコードが複雑になっている。

最後の行は昇順ではない？

例1の dp の最後の行の値は昇順に並んでいるので、

0 1 2 3 4 5 6 7
0 0
1 0 13
2 0 17 30
3 0 17 29 30
4 0 10 17 27 29 39 40

最大値は右から見て最初に登場した値とする、としてはまった。昇順の傾向があるだけで、たとえば例3では昇順になっていないのが確認できる。

0 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
0 0
1 0 8000
2 0 8000 11000 19000
3 0 8000 11000 10000 19000 18000 21000 29000
4 0 8000 11000 10000 13000 19000 18000 21000 21000 24000 23000 29000 32000 31000 34000 42000
5 0 8000 11000 10000 13000 16000 19000 18000 21000 24000 21000 24000 27000 23000 26000 29000 29000 32000 35000 31000 34000 37000 34000 37000 40000 39000 42000 45000 48000 47000 50000 58000
6 0 8000 11000 10000 13000 16000 14000 19000 18000 21000 24000 21000 24000 27000 23000 26000 29000 25000 24000 27000 30000 29000 32000 35000 31000 34000 37000 33000 34000 37000 40000 38000 39000 35000 38000 41000 37000 40000 43000 42000 45000 48000 47000 43000 46000 49000 50000 48000 51000 48000 51000 54000 53000 58000 56000 59000 62000 61000 64000
7 0 8000 11000 10000 13000 16000 14000 25000 18000 21000 24000 21000 24000 27000 23000 26000 33000 29000 25000 24000 36000 27000 30000 35000 38000 41000 31000 34000 37000 39000 34000 37000 44000 40000 38000 43000 39000 46000 49000 35000 38000 41000 46000 37000 40000 49000 52000 43000 48000 51000 54000 47000 50000 49000 52000 55000 54000 50000 48000 57000 60000 51000 56000 59000 62000 48000 51000 58000 54000 59000 62000 53000 65000 63000 64000 60000 63000 66000 62000 65000 68000 67000 70000 61000 73000 72000 68000 64000 71000 74000 75000 73000 76000 73000 76000 79000
8 0 8000 11000 10000 13000 16000 14000 25000 18000 18000 21000 24000 21000 24000 27000 23000 26000 33000 29000 26000 25000 24000 36000 27000 30000 35000 29000 38000 41000 28000 31000 34000 31000 34000 37000 39000 34000 37000 44000 32000 40000 38000 43000 39000 43000 46000 49000 36000 35000 39000 42000 41000 46000 37000 40000 49000 52000 43000 48000 51000 42000 45000 54000 41000 44000 47000 51000 50000 47000 49000 43000 52000 55000 54000 42000 50000 54000 57000 60000 48000 53000 56000 59000 56000 59000 62000 49000 52000 51000 58000 55000 54000 59000 62000 53000 57000 65000 63000 52000 55000 64000 62000 58000 56000 61000 60000 57000 64000 67000 66000 53000 62000 65000 56000 59000 68000 67000 70000 58000 67000 70000 73000 61000 66000 69000 72000 72000 68000 65000 64000 68000 71000 74000 67000 75000 73000 70000 73000 76000 68000 66000 75000 78000 69000 74000 77000 76000 80000 79000
9 0 8000 11000 10000 13000 16000 14000 25000 18000 18000 21000 24000 23000 21000 24000 27000 23000 26000 33000 29000 26000 25000 31000 24000 36000 27000 30000 35000 29000 38000 41000 34000 28000 31000 34000 33000 31000 34000 37000 36000 39000 39000 34000 37000 44000 32000 40000 38000 43000 39000 43000 46000 49000 48000 36000 35000 41000 39000 42000 41000 46000 47000 37000 40000 49000 52000 43000 48000 51000 44000 42000 45000 54000 47000 50000 44000 47000 51000 50000 47000 56000 52000 43000 52000 55000 54000 42000 50000 54000 57000 60000 59000 53000 56000 59000 58000 56000 59000 62000 61000 64000 52000 51000 54000 58000 55000 54000 59000 62000 53000 57000 65000 63000 62000 55000 64000 62000 60000 58000 67000 61000 63000 61000 66000 64000 67000 66000 69000 72000 62000 65000 58000 56000 59000 68000 67000 70000 69000 67000 70000 73000 72000 75000 69000 72000 71000 74000 72000 65000 68000 77000 65000 64000 68000 71000 74000 73000 70000 75000 73000 72000 70000 73000 76000 75000 78000 77000 75000 78000 77000 80000 83000 77000 76000 79000 82000 80000 79000 82000
10 0 8000 11000 10000 13000 16000 14000 25000 18000 18000 21000 24000 23000 27000 21000 24000 27000 23000 26000 33000 29000 26000 25000 31000 24000 36000 27000 30000 35000 29000 38000 41000 34000 28000 31000 34000 38000 31000 34000 37000 37000 39000 40000 43000 34000 37000 44000 32000 40000 38000 43000 39000 43000 46000 49000 48000 36000 35000 52000 39000 42000 41000 46000 47000 37000 45000 49000 52000 50000 43000 48000 51000 44000 42000 45000 54000 48000 50000 44000 47000 51000 54000 47000 56000 50000 53000 60000 43000 56000 55000 54000 42000 50000 54000 57000 60000 59000 53000 56000 59000 63000 56000 59000 62000 62000 64000 52000 56000 65000 68000 61000 55000 59000 62000 60000 58000 61000 65000 63000 66000 55000 64000 62000 66000 58000 67000 61000 64000 61000 71000 64000 67000 66000 70000 72000 66000 70000 73000 76000 75000 68000 67000 70000 69000 67000 70000 73000 73000 75000 69000 72000 76000 79000 72000 70000 75000 78000 71000 69000 72000 81000 74000 77000 71000 75000 78000 77000 74000 83000 76000 79000 78000 77000 75000 79000 82000 81000 83000 77000 81000 84000 87000 86000 80000 83000

したがって、

dp[N][W.downto(0).find { |i| dp[N][i] }]  # => 83000

ではなく、

dp[N].max_by { |e| e || 0 }  # => 87000

としないといけない。

鉄則本風の実装 (AC)

991 ms
N, W = gets.split.collect(&:to_i)                    # => [4, 7]
WV = N.times.collect { gets.split.collect(&:to_i) }  # => [[3, 13], [3, 17], [5, 29], [1, 10]]
WV.unshift(nil)                                      # => [nil, [3, 13], [3, 17], [5, 29], [1, 10]]
dp = Array.new(N.next) { Array.new(W.next, -Float::INFINITY) } # -無限大 で初期化する
dp[0][0] = 0
(1..N).each do |y|                  # 縦軸: 1..アイテム数
  (0..W).each do |x|                # 横軸: 0..容量
    w, v = WV[y]                    # w:大きさ v:価値
    if x < w
      # y 番目のアイテムが使えない
      dp[y][x] = dp[y - 1][x]
    else
      # y 番目のアイテムが使えるが、使わない or 使う
      dp[y][x] = [dp[y - 1][x], (dp[y - 1][x - w]) + v].max
    end
  end
end
p dp[N].max                                          # => 40
0 1 2 3 4 5 6 7
0 0 -INF -INF -INF -INF -INF -INF -INF
1 0 -INF -INF 13 -INF -INF -INF -INF
2 0 -INF -INF 17 -INF -INF 30 -INF
3 0 -INF -INF 17 -INF 29 30 -INF
4 0 10 -INF 17 27 29 39 40

dp を負の無限大で初期化しておくことで nil チェックを省いている。若干遅くなっているようにも見えるが簡潔に書けるメリットは大きい。とりわけコンテスト中であればこの方法を使いたい。

分岐条件まとめ

条件 コード 向き
使えない x < w && dp[y][x] = dp[y - 1][x] ⬇️
使えるが使わない x >= w && dp[y][x] = dp[y - 1][x] ⬇️
使えるので使う x >= w && dp[y][x] = dp[y - 1][x - w] + v ↘️

Discussion