結果

問題 No.626 Randomized 01 Knapsack
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-14 17:15:29
言語 Go
(1.22.1)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 3,244 bytes
コンパイル時間 15,404 ms
コンパイル使用メモリ 202,012 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-24 05:48:03
合計ジャッジ時間 17,227 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 4 ms
4,376 KB
testcase_11 AC 8 ms
4,380 KB
testcase_12 AC 9 ms
4,376 KB
testcase_13 AC 9 ms
4,380 KB
testcase_14 AC 8 ms
4,380 KB
testcase_15 AC 8 ms
4,376 KB
testcase_16 AC 8 ms
4,380 KB
testcase_17 AC 8 ms
4,376 KB
testcase_18 AC 8 ms
4,380 KB
testcase_19 AC 9 ms
4,376 KB
testcase_20 AC 9 ms
4,376 KB
testcase_21 AC 9 ms
4,380 KB
testcase_22 AC 9 ms
4,380 KB
testcase_23 AC 9 ms
4,376 KB
testcase_24 AC 8 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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))
}
0