問題: ナップサック問題 (Python)

ナップサック問題 (Python)

問題

1行目に品物の数 n とナップサックの容量、続く n 行に各品物の重さと価値を入力として受け取ります。動的計画法を使って、重さの合計が容量以内で価値の合計が最大になる品物の組み合わせを求め、価値の最大値と選んだ品物の番号（1から始まる）を表示してください。

入力例

出力例

価値の最大値: 11
選んだ品物: [1, 4]

参照コード

コピーはできません。自分でタイピングしてください。

def knapsack(items, capacity):
    """動的計画法で容量以内の価値の最大値と選んだ品物を求める"""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if weight <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - weight] + value)
    chosen = []
    c = capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i)
            c -= items[i - 1][0]
    return dp[n][capacity], chosen[::-1]

def main():
    n, capacity = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    best, chosen = knapsack(items, capacity)
    print(f"価値の最大値: {best}")
    print(f"選んだ品物: {chosen}")

if __name__ == "__main__":
    main()

ナップサック問題 (Python)

問題

入力例

出力例

参照コード

入力エリア