結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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