DPテーブルの舐め方にどう違いが出るのかなと思ったので解いてみる。
整数ナップサック問題
容量がのナップサックに価値
, 重さ
の品物を入れていき、容量に収まる範囲で価値を最大化する問題。同じ商品はなんども選択できる。
提出コード
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
def main():
n, w = list(map(int, input().strip().split()))
dp = [[0] * (w+5) for _ in range(n+5)]
items = [[] for _ in range(n)]
for i in range(n):
items[i] = list(map(int, input().strip().split()))
for i in range(1, n+1):
for j in range(1, w+1):
if j-items[i-1][1] < 0:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-items[i-1][1]]+items[i-1][0])
print(dp[n][w])
if __name__ == '__main__':
main()
0-1ナップサック問題
整数ナップサック問題とは商品を1回しか選択できないという点で異なる。
提出コード
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
def main():
n, w = list(map(int, input().strip().split()))
dp = [[0] * (w+5) for _ in range(n+5)]
items = [[] for _ in range(n)]
for i in range(n):
items[i] = list(map(int, input().strip().split()))
for i in range(1, n+1):
for j in range(1, w+1):
if j-items[i-1][1] < 0:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i-1][1]]+items[i-1][0])
print(dp[n][w])
if __name__ == '__main__':
main()
何が違うの？
item[i-1]をナップサックに入れる時の遷移元が異なっている。整数ナップサックなら遷移元はdp[i][j-items[i-1][1]]で、0-1ならdp[i-1][j-items[i-1][1]]。
整数ナップサックでは同じアイテムを何回も選択できるので、dp[i][j-items[i-1][1]]からdpテーブルの同じ行へ遷移できる。dp[i-1][j-items[i-1][1]]はdp[i][j-items[i-1][1]]より大きくならないので、0-1ナップサック問題のように遷移式に含める必要がない。
