結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2017-06-21 22:47:41 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 1,482 ms |
コンパイル使用メモリ | 68,552 KB |
実行使用メモリ | 41,684 KB |
最終ジャッジ日時 | 2024-10-02 11:53:05 |
合計ジャッジ時間 | 2,608 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:78:30: warning: ‘max’ may be used uninitialized in this function [-Wmaybe-uninitialized] 78 | std::cout << max << std::endl; | ^~~ main.cpp:74:22: warning: ‘min’ may be used uninitialized in this function [-Wmaybe-uninitialized] 74 | std::cout << min << std::endl; | ^~~
ソースコード
#include <iostream> #include <string> #include <sstream> #include <vector> #include <utility> typedef unsigned int uint; int main() { int num_loop; std::cin >> num_loop; std::vector< std::pair<int, int> > item; int maxValue; int tmpW = 0; for (uint i=0; i<num_loop; ++i) { int v, w; std::cin >> v; std::cin >> w; item.emplace_back(v, w); tmpW += w; } std::cin >> maxValue; std::vector< std::vector< int > > c(num_loop+1, std::vector< int >(tmpW+1, 0)); std::vector< std::vector< int > > d(num_loop+1, std::vector< int >(tmpW+1, 0)); for (uint i=0; i<c.size(); ++i) { c[i][0] = 0; } for (uint j=0; j<c[0].size(); ++j) { c[0][j] = 0; } for (uint i=1; i<c.size(); ++i) { for (uint j=1; j<c[i].size(); ++j) { if (j < item[i-1].second) { c[i][j] = c[i-1][j]; d[i][j] = 0; } else { int n = c[i-1][j]; int y = c[i-1][j-item[i-1].second] + item[i-1].first; if (n <= y) { c[i][j] = y; d[i][j] = 1; } else { c[i][j] = n; d[i][j] = 0; } } } } int min, max; bool flag = false; for (uint j=1; j<c[num_loop].size(); ++j) { if (c[num_loop][j] == maxValue) { if (!flag) { min = j; flag = true; } } else if (c[num_loop][j] > maxValue) { if (flag) { max = j-1; flag = false; } } } std::cout << min << std::endl; if (flag) { std::cout << "inf" << std::endl; } else { std::cout << max << std::endl; } return 0; }