結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
|
提出日時 | 2021-08-21 17:32:13 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 1,173 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-10-15 08:09:45 |
合計ジャッジ時間 | 2,987 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
from bisect import bisectfrom collections import defaultdictfrom itertools import accumulatedef solve(n, W, vw):vw.sort(key=lambda x: x[0] / x[1], reverse=True)vs = []ws = []wei_to_val = defaultdict(int)wei_to_val[0] = 0for v, w in vw:vs.append(v)ws.append(w)cum_v, cum_w = [0] + list(accumulate(vs)), [0] + list(accumulate(ws))cum_v.append(cum_v[-1])res = cum_v[bisect(cum_w, W) - 1]for i, (v, w) in enumerate(vw):cur_w = W + cum_w[i]del_v = cum_v[i]for w2, v2 in list(wei_to_val.items()):if w2 + w > W: continuej = bisect(cum_w, cur_w - w2) - 1tmp_ans = v2 + cum_v[j] - del_vif j < n - 1:plus = vs[j] * (cur_w - w2 - cum_w[j]) / ws[j]else:plus = 0if tmp_ans + plus <= res:del wei_to_val[w2]continueres = max(res, tmp_ans)wei_to_val[w2 + w] = max(wei_to_val[w2 + w], v2 + v)return resn, W = map(int, input().split())vw = [list(map(int, input().split())) for i in range(n)]print(solve(n, W, vw))