結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
|
提出日時 | 2021-08-29 03:27:21 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 807 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 13,816 KB |
最終ジャッジ日時 | 2024-11-22 01:53:51 |
合計ジャッジ時間 | 2,420 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
import syssys.setrecursionlimit(10 ** 7)n, cap = map(int, input().split())best = 0goods = [list(map(int, input().split())) for i in range(n)]goods.sort(key=lambda x: x[0] / x[1], reverse=True)v_cum = [0]def dfs(ind, v, w):global bestif w > cap: returnif ind == n: best = max(best, v); returnv_l = vw_new = cap - wcur = indwhile cur < n and 0 <= w_new - goods[cur][1]:w_new -= goods[cur][1]v_l += goods[cur][0]cur += 1cur -= 1if cur == n and w_new == 0: bese = max(best, v_l); returnopt = v_l + goods[cur][0] * (w_new / goods[cur][1])if opt <= best: returndfs(ind + 1, v + goods[ind][0], w + goods[ind][1])dfs(ind + 1, v, w)for i in range(n): v_cum.append(v_cum[-1] + goods[i][0])dfs(0, 0, 0)print(best)