Problem p03732 (python)

Fixed submission:
# -*- coding: utf-8 -*-
"""
https://abc060.contest.atcoder.jp/tasks/arc073_b

"""
import sys
from sys import stdin
input = stdin.readline


def normal_dp(items, N, W):
    dp = [[0] * (W+1) for _ in range(N+1)]

    for y in range(1, N+1):
        w = items[y-1][0]
        v = items[y-1][1]
        for x in range(1, W+1):
            if x >= w:
                dp[y][x] = max(dp[y-1][x-w] + v, dp[y-1][x])
            else:
                dp[y][x] = dp[y-1][x]
    return dp[-1][-1]


def solve(items, N, W):
    items.sort(reverse=True)

    c_items = [[] for _ in range(4)] #  同じ重さのアイテムをまとめたもの、vで降順ソート済。[0]が一番軽いアイテムで[3]が+3だけ重い。
    min_w = items[-1][0]
    for w, v in items:
        c_items[w - min_w].append(v)
    for l in c_items:
        l.append(0)

    # ある重さのアイテムをn個選択したときのベストなvの値を計算しておく
    accumulated_v = [[0] for _ in range(4)]
    for i in range(4):
        for j, v in enumerate(c_items[i], start=1):
            accumulated_v[i].append(accumulated_v[i][-1] + v)

    total_values = []
    for iw0 in range(len(c_items[0])):
        for iw1 in range(len(c_items[1])):
            for iw2 in range(len(c_items[2])):
                for iw3 in range(len(c_items[3])):
                    total_w = (iw0 * min_w) + (iw1 * (min_w+1)) + (iw2 * (min_w+2)) + (iw3 * (min_w+3))
                    if total_w <= W:
                        total_v = accumulated_v[0][iw0] + accumulated_v[1][iw1] + accumulated_v[2][iw2] + accumulated_v[3][iw3]
                        total_values.append(total_v)
    return max(total_values)



def main(args):
    items = []
    N, W = map(int, input().split())
    for _ in range(N):
        w, v = map(int, input().split())
        items.append([w, v])
    items.sort()
    ans = solve(items, N, W)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
https://abc060.contest.atcoder.jp/tasks/arc073_b
01ナップサック問題
Wの上限値が非常に大きいケース(～1e9)。Wを横軸にしてdpテーブルを作成すると非常に大きくなってしまうので、メモリ消費や処理時間が問題になる。
価値に対する重さが最小になるようにdpを計算する
"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple
from operator import itemgetter
from bisect import bisect_right


def solve(items, W, max_v):
    # 表を上から組み立てていく方式
    n = len(items)
    dp = [[float('inf')]*(n*max_v + 1) for _ in range(n+1)] #  横軸が で縦軸が の種類
    dp[0][0] = 0

    for i, item in enumerate(items):
        for j in range(n * max_v + 1):
            if j < item.value:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-item.value]+item.weight)

    for j in range(n * max_v + 1):
        if dp[n][j] <= W:
            result = j
    return result

    # dpテーブル値は基本的に右にいくほど増加するが、infが入っているセルがあるのでbinsectは使用できない
    # result = bisect_right(dp[n], W)
    # return result-1

item = namedtuple('item', ['weight', 'value'])
def main(args):
    # items = [item(2, 3), item(1, 2), item(3, 4), item(2, 2)]
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        w, v = map(int, input().split())
        items.append(item(w, v))
    max_v = max(items, key=itemgetter(1)).value #  items内で最大のvalueを持つ項目を探し、そのアイテムのvalue値をゲットする

    result = solve(items, W, max_v)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])