Submission #868632

#	Time	Username	Problem	Language	Result	Execution time	Memory
868632		iamjiamingliu	Knapsack (NOI18_knapsack)	Pypy 3	0 / 100	48 ms	20432 KiB

knapsack

import math

# Used by bounded knapsack
def zero_one_knapsack(weights, values, weight_limit: int) -> int:
    w_gcd = math.gcd(*weights, weight_limit)
    weights = [w // w_gcd for w in weights]
    weight_limit //= w_gcd
    dp = [0] * (weight_limit + 1)
    for item_i in range(len(weights)):
        new_dp = dp.copy()
        for w in range(weights[item_i], weight_limit + 1):
            new_dp[w] = max(dp[w], dp[w - weights[item_i]] + values[item_i])
        dp = new_dp
    return dp[weight_limit]

def bounded_knapsack(weights, values, quantities, weight_limit: int) -> int:
    adjusted_items = []
    for w, v, q in zip(weights, values, quantities):
        for pow_two in range(q.bit_length()):
            adjusted_items.append((w * (1 << pow_two), v * (1 << pow_two)))
    return zero_one_knapsack([item[0] for item in adjusted_items], [item[1] for item in adjusted_items], weight_limit)


if __name__ == '__main__':
    weight_limit, items_cnt = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(items_cnt)]
    vs = [i[0] for i in items]
    ws = [i[1] for i in items]
    qs = [i[2] for i in items]
    print(bounded_knapsack(ws, vs, qs, weight_limit))

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27