💧
ABC015-D: 高橋くんの苦悩 解説
問題(概要)
正整数
, W と K 個の正整数の組 N が与えられます. (A_1, B_1), (A_2, B_2) ,...,(A_N, B_N)
この個の組から N 個まで選びます. K
この時,選んだ組のの総和は A 以下である必要があります. W
この条件下のの総和の最大値を出力してください. B
制約
1 \leq W \leq 10000
1 \leq K \leq N \leq 50
1 \leq A_i \leq 1000
1 \leq B_i \leq 100
解説
- ナップサック問題に選べる数の制約がついた感じの問題
- この制約だと次のような動的計画法で解ける
-
の組まででdp[i][j][w] : (A_i, B_i) 組選んだとき,j の総和がA の時のw の総和の最大値B dp[i][j][w] \leftarrow max(dp[i][j][w], dp[i-1][j][w], dp[i-1][j-1][w - A_i] + B_i)
-
- 計算量は
, 制約の最大値であっても実行時間制限の2秒以内に十分間に合いそうO(NKW)
コード
Tips
- 実行時間がC++でも124msとなっている
- この解答ではdpテーブルが3次元で表現されている.
- 実は
の操作を小さい順ではなく大きい順で行うことで,dpテーブルにおけるj の情報は不要になるため,2次元で表現ができる(14行目の部分).i - 大きい順にしないで2次元で表現すると同じ組を2度選んでしまう可能性がある
- たまに役立つので覚えておくとヨシ
- これだと61ms
Discussion