Edit

【pythonでABC060を解説】D - Simple Knapsack

問題概要

問題ページ

D - Simple Knapsack
D - Simple Knapsack

問題ページへ移動する

問題文

あなたは \(N\) 個の物と、強度 \(W\) のバッグを持っています。
\(i\) 個目の物は、重さが \(w_i\) で価値が \(v_i\) です。

あなたは、物のうちいくつかを選び、バッグに入れます。
ただし、選んだ物の重さの和は \(W\) 以下でなくてはいけません。

あなたは、バッグに入れた物の価値の総和を最大化したいです。

制約

  • \(1 ≦ N ≦ 100\)
  • \(1 ≦ W ≦ 10^9\)
  • \(1 ≦ w_i ≦ 10^9\)
  • すべての \(i = 2,3,...,N\) について、\(w_1 ≦ w_i ≦ w_1 + 3\)
  • \(1 ≦ v_i ≦ 10^7\)
  • \(W, w_i, v_i\) はすべて整数である

問題の考察

ACコード

import sys
import collections
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(n):
        wv, vv = list(map(int, input().rstrip('\n').split()))
        d[wv] += [vv]
    key = []
    for dw, dv in d.items():
        d[dw] = [0] + list(itertools.accumulate(sorted(dv, reverse=True)))
        key.append(dw)
    for i in range(4 - len(d)):
        d[-i-1] += [0]
        key.append(-i-1)
    mx = 0
    for i in range(len(d[key[0]])):
        for j in range(len(d[key[1]])):
            for k in range(len(d[key[2]])):
                for l in range(len(d[key[3]])):
                    if i * key[0] + j * key[1] + k * key[2] + l * key[3] <= w:
                        total = d[key[0]][i] + d[key[1]][j] + d[key[2]][k] + d[key[3]][l]
                        mx = max(mx, total)
    print(mx)


if __name__ == '__main__':
    solve()

-Edit
-