結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2018-05-14 22:12:01 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 782 bytes |
コンパイル時間 | 1,216 ms |
コンパイル使用メモリ | 159,580 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-28 11:50:43 |
合計ジャッジ時間 | 2,465 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; int N, V, W = 0; int MIN = INT_MAX, MAX = 0; int value[100001] = {0}; int weight[100001] = {0}; int dp[100005] = {0}; int main(void){ cin >> N; for(int i = 0; i < N; ++i){ cin >> value[i]; cin >> weight[i]; W += weight[i]; } cin >> V; for(int i = 0; i < N; ++i){ for(int j = W; j >= weight[i]; j--){ dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } for(int i = 1; i <= W; ++i){ if(dp[i] == V){ if(MIN > i) MIN = i; if(MAX < i) MAX = i; } } if(dp[MAX + 1] == 0) cout << MIN << endl << "inf" << endl; else cout << MIN << endl << MAX << endl; return 0; }