電気ひつじ牧場

技術メモと日常のあれこれ

整数ナップサック問題と0-1ナップサック問題を解いて比較する

DPテーブルの舐め方にどう違いが出るのかなと思ったので解いてみる。

整数ナップサック問題

容量が Wのナップサックに価値 v_i, 重さ w_iの品物を入れていき、容量に収まる範囲で価値を最大化する問題。同じ商品はなんども選択できる。

onlinejudge.u-aizu.ac.jp

提出コード

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回しか選択できないという点で異なる。

onlinejudge.u-aizu.ac.jp

提出コード

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ナップサック問題のように遷移式に含める必要がない。