結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"bufio"
"fmt"
"os"
"sort"
)
// n<=40 meet in the middle
func 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 := 0
relax := func(i, v, w int) (int, bool) {
res := v
flag := true
for i < n {
if w == 0 {
break
}
if w >= goods[i][1] {
w -= goods[i][1]
res += goods[i][0]
i++
continue
}
flag = false
res += 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 int
fmt.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))
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0