結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2017-06-14 00:36:02 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 1,264 bytes |
コンパイル時間 | 611 ms |
コンパイル使用メモリ | 75,024 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 17:04:54 |
合計ジャッジ時間 | 1,850 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:16:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 16 | scanf("%d %d", &v[i], &w[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <iomanip> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <map> #include <set> using namespace std; int main() { int n; cin >> n; vector<int> v(n), w(n); for (int i = 0; i < n; i++) { scanf("%d %d", &v[i], &w[i]); } int mx_v; cin >> mx_v; vector<int> dp(100010, 0); for (int i = 0; i < n; i++) { for (int j = 100000 - *max_element(w.begin(), w.end()); j >= 0; j--) { dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]); } } if(*max_element(dp.begin(), dp.end()) == mx_v){ for(int i = 0; i < 100000; i++){ if(dp[i] == mx_v){ cout << i << endl << "inf" << endl; return 0; } } }else{ int a = 0; int b = 0; for(int i = 0; i < 100000; i++){ if(dp[i] == mx_v){ if(dp[i] == 0){ cout << 1 << endl << *min_element(w.begin(), w.end()) - 1 << endl; return 0; } if(a == 0)a = i; }else if(a > 0 && dp[a] < dp[i]){ cout << a << endl << i - 1 << endl; return 0; } } } }