コンテンツにスキップ

ABC479 C - Bento Packing

サイト
AtCoder
コンテスト
ABC479
問題
C - Bento Packing
難易度
-

NN 個のおかずがあり、ii 個目のおいしさは AiA_i、体積は BiB_i です。体積の合計が WW 以下になるようにおかずを選ぶとき、おいしさの合計の最大値を求める問題です。1 つも選ばなくてもかまいません(1≤N≤201 \le N \le 20、1≤W,Ai,Bi≤1091 \le W, A_i, B_i \le 10^9)。

N≤20N \le 20 と小さいので、おかずの選び方 2N2^N 通りをすべて調べられます。それぞれについて体積の合計とおいしさの合計を求め、体積の合計が WW 以下のもののうち、おいしさの合計の最大値が答えです。

選び方は、00 以上 2N2^N 未満の整数 ii で表します。ii を 2 進数で書いたとき下から jj 桁目が 11 なら jj 個目のおかずを選ぶ、と決めれば、ii を 00 から 2N−12^N - 1 まで動かすことですべての選び方を 1 回ずつ調べられます。計算量は O(2NN)O(2^N N) です。

WW や BiB_i が大きいので、体積を添字にするナップサック DP は使えません。

Python
N, W = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
ans = 0
for 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 で、ii の下から jj 桁目(0 始まり)が 11 かどうか、つまり jj 個目のおかずを選ぶかどうかを調べています。a がおいしさの合計、b が体積の合計です。i = 0 は何も選ばない場合にあたり、このとき a = 0 なので、ans の初期値 00 と同じです。