ABC479 C - Bento Packing
- サイト
- AtCoder
- コンテスト
- ABC479
- 問題
- C - Bento Packing
- 難易度
- -
個のおかずがあり、 個目のおいしさは 、体積は です。体積の合計が 以下になるようにおかずを選ぶとき、おいしさの合計の最大値を求める問題です。1 つも選ばなくてもかまいません(、)。
と小さいので、おかずの選び方 通りをすべて調べられます。それぞれについて体積の合計とおいしさの合計を求め、体積の合計が 以下のもののうち、おいしさの合計の最大値が答えです。
選び方は、 以上 未満の整数 で表します。 を 2 進数で書いたとき下から 桁目が なら 個目のおかずを選ぶ、と決めれば、 を から まで動かすことですべての選び方を 1 回ずつ調べられます。計算量は です。
や が大きいので、体積を添字にするナップサック DP は使えません。
Python
N, W = map(int, input().split())AB = [tuple(map(int, input().split())) for i in range(N)]ans = 0for i in range(1 << N): a = 0 b = 0 for j in range(N): if (i >> j) & 1: a += AB[j][0] b += AB[j][1] if b <= W: ans = max(ans, a)print(ans)(i >> j) & 1 で、 の下から 桁目(0 始まり)が かどうか、つまり 個目のおかずを選ぶかどうかを調べています。a がおいしさの合計、b が体積の合計です。i = 0 は何も選ばない場合にあたり、このとき a = 0 なので、ans の初期値 と同じです。