ABC145 E - All-you-can-eat

問題原文

E - All-you-can-eat

問題要旨

ナップサック問題を解いてください。
ただし、最後に入れる品物（その品物を入れるとナップサックの容量以上になる）は重さを無視して良いものとします。

考えたこと

• ナップサック問題を普通に解いて、どの品物を入れたか復元。使ってないものから価値が最も高いものを選べばいいのでは？（嘘解法）（価値を先に考えた結果、ぴったり入れきってしまって全部入らない場合などがある）

難しいこと

• 最後だけ特別扱いできる

考えるべきこと

解法１ 二つのdpテーブルで挟む

• 「最後にどの品物を入れるか」を全探索したい。
• 「前から商品を見たDPテーブル()」と「後ろから商品を見たDPテーブル()」があれば、 商品 を最後に入れる場合の価値の総和は、 となり、高速に計算できる。

実装

dpテーブルをいつもより一つ分大きくとると書きやすい。

N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

# dp1[i][j] := 商品0 ~ i が対象
# dp2[i][j] := 商品i ~ N が対象(順番はそのまま)
# out-of-index 対策に余分に取っておく
dp1 = [[0] * (W + 1) for i in range(N + 2)]
dp2 = [[0] * (W + 1) for i in range(N + 2)]

# dp1を埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp1[i + 1][j + wi] = max(dp1[i + 1][j + wi], dp1[i][j] + vi)
        dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j])

# dp2を埋める
for i in range(N + 1, 1, -1):
    wi, vi = items[i - 2]
    for j in range(W + 1):
        if j + wi <= W:
            dp2[i - 1][j + wi] = max(dp2[i - 1][j + wi], dp2[i][j] + vi)
        dp2[i - 1][j] = max(dp2[i][j], dp2[i - 1][j])


# 2つのdpテーブルを使って、最後に使う商品を全探索
ans = 0
# ここからは商品を1-indexedとする
for i, (wi, vi) in enumerate(items, start=1):
    for j in range(W):
        ans = max(ans, dp1[i - 1][j] + dp2[i + 1][W - j - 1] + vi)

print(ans)

解法２ ソートしてナップサック

• よく考えると、「使う商品の中で、最も重たいものを最後に入れるのが最適」。
• つまり、あらかじめ入力を重さでソートしておけば、解法１の のみで「各商品を最後に入れる場合の価値の総和の最大値」が求まる。

実装

N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])

dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
# 最後に入れる商品は、残り容量１の時に入れるとしてしまってよい
for i, (wi, vi) in enumerate(items):
    ans = max(ans, dp[i][W - 1] + vi)

print(ans)

所感

「はさみこむdp」とかっていうのかな。いろんな解法に応用できそう。