結果
問題 |
No.626 Randomized 01 Knapsack
|
ユーザー |
![]() |
提出日時 | 2017-12-29 18:33:58 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 1,344 bytes |
コンパイル時間 | 1,172 ms |
コンパイル使用メモリ | 65,504 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 03:32:12 |
合計ジャッジ時間 | 2,094 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
//v / wが大きいほうから探索 → 分岐限定で枝刈り → 上界の計算を厳しくする(O(n)かけて計算) #include <iostream> #include <algorithm> #include <functional> using namespace std; struct Baggage { double key; long long v, w; Baggage() {} Baggage(long long v, long long w) { this->v = v; this->w = w; key = (double)v / w; } bool operator>(const Baggage &r) const { return key > r.key; } }; int n; long long w; Baggage bag[5000]; long long maxSumV; void maxV(int id, long long remW, long long sumV) { if (id == n) { maxSumV = max(maxSumV, sumV); return; } long double kanwaSumV = 0; long double kanwaRemW = remW; for (int i = id; i < n; i++) { if (kanwaRemW >= bag[i].w) { kanwaRemW -= bag[i].w; kanwaSumV += bag[i].v; } else { kanwaSumV += bag[i].v * (kanwaRemW / bag[i].w); break; } } long long kanwaAns = kanwaSumV + sumV; if (kanwaAns <= maxSumV) { return; } if (remW >= bag[id].w) { maxV(id + 1, remW - bag[id].w, sumV + bag[id].v); } maxV(id + 1, remW, sumV); } int main() { int i; cin >> n >> w; long long sumW = 0; for (i = 0; i < n; i++) { long long v, w; cin >> v >> w; bag[i] = Baggage(v, w); sumW += w; } w = min(w, sumW); sort(bag, bag + n, greater<Baggage>()); maxV(0, w, 0); cout << maxSumV << endl; return 0; }