結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
|
提出日時 | 2022-04-28 10:37:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 1,368 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 81,248 KB |
最終ジャッジ日時 | 2024-06-28 07:54:06 |
合計ジャッジ時間 | 2,989 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
n,W = map(int,input().split())l = []for _ in range(n):v,w = map(int,input().split())if w <= W:l.append((v,w))n = len(l)l.sort(key = lambda x:x[0] / x[1],reverse = True)def kanwa(i,nowv,noww):flag = Falsefor j in range(i,n):v,w = l[j]if w == W - noww:flag = Trueif w < W - noww:nowv += vnoww += welse:rate = (W - noww) / wnowv += v * ratenoww = Wbreakreturn nowv,flagimport syssys.setrecursionlimit(10 ** 8)zanteikai = 0inf = 10 ** 18def calc(i,nowv,noww):global zanteikaiif i == n:if nowv > zanteikai:zanteikai = nowvreturn nowvkanwakai,flag = kanwa(i,nowv,noww)if flag:if kanwakai > zanteikai:zanteikai = kanwakaireturn int(kanwakai)if kanwakai < zanteikai:return -infv,w = l[i]tmp = -infif noww + w <= W:u = calc(i + 1,nowv + v,noww + w)if u > tmp:tmp = uif tmp > zanteikai:zanteikai = tmpu = calc(i + 1,nowv,noww)if u > tmp:tmp = uif tmp > zanteikai:zanteikai = tmpreturn tmpnow = 0for v,w in l:if now + w <= W:now += wzanteikai += vans = calc(0,0,0)print(ans)