結果

問題 No.527 ナップサック容量問題
ユーザー AEn
提出日時 2022-08-24 16:49:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 329 ms / 2,000 ms
コード長 595 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 143,232 KB
最終ジャッジ日時 2024-10-12 01:26:14
合計ジャッジ時間 7,581 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
item = [list(map(int, input().split())) for _ in range(N)]
V = int(input())
dp = [[0]*(10**5+1) for _ in range(N+1)]
sm_v, sm_w = 0, 0
for i in range(1, N+1):
    v, w = item[i-1]
    sm_v += v
    sm_w += w
    for j in range(10**5+1):
        if j>=w:
            dp[i][j] = max(dp[i-1][j-w]+v, dp[i][j])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

for i in range(1,10**5+1):
    if dp[-1][i] == V:
        print(i)
        break
if dp[-1][sm_w] == V:
    print('inf')
else:
    for i in range(10**5, 0, -1):
        if dp[-1][i] == V:
            print(i)
            break
0