結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
|
提出日時 | 2017-12-22 04:11:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 2,234 bytes |
コンパイル時間 | 2,374 ms |
コンパイル使用メモリ | 200,292 KB |
最終ジャッジ日時 | 2025-01-05 06:13:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; struct Product { ll v; ll w; bool operator<(const Product& p) const { return v * p.w < w * p.v; } bool operator>(const Product& p) const { return v * p.w > w * p.v; } }; ostream& operator<<(ostream& os, const Product& p) { os << "<" << p.v << ", " << p.w << ">"; return os; } ll ans = 0; int N; ll W; void dfs(const vector<Product>& product, const int ind, const ll weight, const ll value) { if (ind == N) { ans = max(ans, value); return; } if (weight + product[ind].w <= W) { ld relaxed = value + product[ind].v; ll use = weight + product[ind].w; for (int i = ind + 1; i < N; i++) { if (use + product[i].w <= W) { use += product[i].w; relaxed += product[i].v; } else { relaxed += (ld)(product[i].v) / product[i].w * (W - use); use = W; break; } } if (relaxed > ans) { dfs(product, ind + 1, weight + product[ind].w, value + product[ind].v); } } ld relaxed = value; ll use = weight; for (int i = ind + 1; i < N; i++) { if (use + product[i].w <= W) { use += product[i].w; relaxed += product[i].v; } else { relaxed += (ld)(product[i].v) / product[i].w * (W - use); use = W; break; } } if (relaxed > ans) { dfs(product, ind + 1, weight, value); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> W; vector<Product> product; for (int i = 0; i < N; i++) { ll v, w; cin >> v >> w; if (w > W) { continue; } product.push_back(Product{v, w}); } N = product.size(); sort(product.begin(), product.end(), greater<Product>{}); ll use = 0; for (int i = 0; i < N; i++) { if (use + product[i].w <= W) { ans += product[i].v; use += product[i].w; } } dfs(product, 0, 0, 0); cout << ans << endl; return 0; }