結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2017-06-16 09:03:19 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 313 ms / 2,000 ms |
コード長 | 483 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 77,440 KB |
実行使用メモリ | 157,812 KB |
最終ジャッジ日時 | 2024-10-01 06:36:24 |
合計ジャッジ時間 | 8,880 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#yuki_527 n=int(raw_input()) v=[] w=[] for i in xrange(n): v1,w1=map(int,raw_input().split()) v.append(v1) w.append(w1) V=int(raw_input()) dp=[[0 for i in xrange(101010)] for j in xrange(n+1)] for i in xrange(n): for j in xrange(100002): dp[i+1][j]=max(dp[i+1][j],dp[i][j]) dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]) mn=float('inf') mx=-1 for i in xrange(1,100002): if dp[n][i]==V: mn=min(mn,i) mx=max(mx,i) print mn if mx==100001: print 'inf' else: print mx