結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
|
提出日時 | 2023-02-14 17:15:29 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 3,244 bytes |
コンパイル時間 | 16,203 ms |
コンパイル使用メモリ | 232,740 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-17 06:05:14 |
合計ジャッジ時間 | 17,861 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
package mainimport ("bufio""fmt""os""sort")// n<=40 的情况下,可以 meet in the middlefunc knapsack1(values []int, weights []int, limit int) int {return 0}// vi 很小的情况下,[dp[i][j]] 表示前 i 个物品,达成总价值为 j 时的最小重量func knapsack2(values []int, weights []int, limit int) int {return 0}// wi 很小的情况下,[dp[i][j]] 表示前 i 个物品,取得重量为 j 时的最大价值func knapsack3(values []int, weights []int, limit int) int {return 0}// template <typename V, typename W, typename D = long double>// struct BranchAndBound {// vector<pair<V, W>> c;// V best;// BranchAndBound(const vector<V>& v, const vector<W>& w) {// assert(v.size() == w.size());// vector<int> ord(v.size());// iota(begin(ord), end(ord), 0);// sort(begin(ord), end(ord),// [&](int i, int j) { return D(v[i]) * w[j] > D(v[j]) * w[i]; });// for (auto& i : ord) c.emplace_back(v[i], w[i]);// }// pair<D, bool> relax(int i, V v, W w) {// D ret = v;// bool f = true;// while (i < (int)c.size()) {// if (w == 0) break;// if (w >= c[i].second) {// w -= c[i].second, ret += c[i].first, ++i;// continue;// }// f = false, ret += (D(c[i].first) * w) / c[i].second;// break;// }// return make_pair(ret, f);// }// void dfs(int i, V v, W w) {// if (i == (int)c.size()) {// best = max(v, best);// return;// }// auto [rel, flg] = relax(i, v, w);// if (flg) {// best = max(best, V(rel));// return;// }// if (V(rel) < best) return;// if (w >= c[i].second) dfs(i + 1, v + c[i].first, w - c[i].second);// dfs(i + 1, v, w);// return;// }// V run(W w) {// dfs(0, best = 0, w);// return best;// }// };// 分枝限定法 n<=2000,vi<=1e9,wi<=1e9,limit<=1e9// O(2^n)func knapsack4(values []int, weights []int, limit int) int {n := len(values)goods := make([][]int, n)for i := range goods {goods[i] = []int{values[i], weights[i]}}sort.Slice(goods, func(i, j int) bool {return goods[i][0]*goods[j][1] > goods[j][0]*goods[i][1]})best := 0relax := func(i, v, w int) (int, bool) {res := vflag := truefor i < n {if w == 0 {break}if w >= goods[i][1] {w -= goods[i][1]res += goods[i][0]i++continue}flag = falseres += goods[i][0] * w / goods[i][1]break}return res, flag}var dfs func(i int, v int, w int)dfs = func(i int, v int, w int) {if i == n {if v > best {best = v}return}rel, flag := relax(i, v, w)if flag {if rel > best {best = rel}return}if rel < best {return}if w >= goods[i][1] {dfs(i+1, v+goods[i][0], w-goods[i][1])}dfs(i+1, v, w)}dfs(0, 0, limit)return best}func main() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n, limit intfmt.Fscan(in, &n, &limit)values := make([]int, n)weights := make([]int, n)for i := range values {fmt.Fscan(in, &values[i], &weights[i])}fmt.Fprintln(out, knapsack4(values, weights, limit))}