AOJ 0-1 Knapsack Problem(DPL_1_B: 0-1 Knapsack Problem)
備忘録
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
回答
import sys sys.setrecursionlimit(10000000) import os import math import bisect import collections import itertools import heapq import re import queue # import fractions ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) # lcm = lambda x, y: (x * y) // fractions.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, W = il() VW = [il() for _ in range(N)] dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] for i in range(N): for w in range(W+1): if w >= VW[i][1]: dp[i+1][w] = max(VW[i][0] + dp[i][w-VW[i][1]], dp[i][w]) else: dp[i+1][w] = dp[i][w] print(dp[N][W]) if __name__ == '__main__': main()
考え方
動的計画法(以下dp)入門として、dpを使用した解法で回答した。
dpの解説については下記を参照し、実装した。
典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita
実装は単純なdpで、
一つ前の値(価値)から次の値(価値)を求めて、表を埋めていった。
以下メモ
品物が4
つ、重さが最大5
まで許容され、
品物((価値, 重さ)
)が(4, 2), (5, 2), (2, 1), (8, 3)
の時。
input
4 5 4 2 5 2 2 1 8 3
dp
w→ i↓[0, 0, 0, 0, 0, 0] [0, 0, 4, 4, 4, 4] [0, 0, 5, 5, 9, 9] [0, 2, 5, 7, 9, 11] [0, 2, 5, 8, 10, 13]