[アルゴリズム]
- これはテクニックの名前であり、具体的なアルゴリズムではありません
要はすべての要素を全探索していたら時間的に間に合わないので、集合を半分ずつに分けて探索するような処理です
- Rubyで再実装しようとしたらTLEになるものがあったので、
特に二分探索に気をつけて実装をする → 実装が重い原因はloopの削減がなされていなかったことでした
|
+
|
#607063
|
|
|
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N;
ll W;
cin >> N >> W;
for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
if (N <= 30) {
int n = N/2;
for (int i = 0; i < 1<<n; i++) {
ll sw = 0, sv = 0;
for (int j = 0; j < n; j++) {
if ((i>>j)&1) {
sw += w[j];
sv += v[j];
}
}
ps[i] = pll(sw, sv);
}
sort(ps, ps+(1<<n));
int m = 1;
for (int i = 1; i < 1<<n; i++) {
if (ps[m-1].second < ps[i].second) ps[m++] = ps[i];
}
ll res = 0;
for (int i = 0; i < 1<<(N-n); i++) {
ll sw = 0, sv = 0;
for (int j = 0; j < N-n; j++) {
if ((i>>j)&1) {
sw += w[n+j];
sv += v[n+j];
}
}
if (sw <= W) {
ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, 1ll<<55))-1)->second;
res = max(res, sv+tv);
}
}
cout << res << endl;
return 0;
}
}
|
|
+
|
#3063489
|
|
|
lines = $stdin.read
array = lines.split("\n")
N,W = array[0].split(" ").map(&:to_i)
item = array[1..N+1].map do |str|
str.split(" ").map(&:to_i)
end
exit 0 if N>30
tmp_h = {}
tmp_a = []
s = 0
S1 = item[0...N/2]
s,len = 0,S1.length
[0,1].repeated_permutation(len) do |a|
tmp_h = {:v => 0, :w => 0}
S1.zip(a).each do |test|
i,bit = test.first,test.last
if bit==1
tmp_h[:v] += i.first
tmp_h[:w] += i.last
end
end
tmp_a << tmp_h if tmp_h[:w] <= W
s += 1
end
tmp_a = tmp_a.sort_by{|m| -m[:v]}
tmp_b = []
ans_v = 0
S2 = item[N/2...N]
s,len = 0,S2.length
[0,1].repeated_permutation(len) do |a|
tmp_h = {:v => 0, :w => 0}
S2.zip(a).each do |test|
i,bit = test.first,test.last
if bit==1
tmp_h[:v] += i.first
tmp_h[:w] += i.last
end
end
if tmp_h[:w] <= W
x = tmp_a.detect{|e| tmp_h[:w] + e[:w] <= W }
ans_v = [ans_v, x[:v] + tmp_h[:v]].max unless x.nil?
end
s += 1
end
puts ans_v
|
N := 荷物の数
W := 荷物の重さ上限値
item := { 価値 vi => 重さ wi } のハッシュマップ
S1 := item[0～N/2] // 荷物の前半分を切り出し
tmp_a := [ { 価値 :v => 0, 重さ :w => 0 } ] のハッシュマップの配列を宣言
for (S1の個数でbit全探索) {
bit := 1 or 0
idx := S1のインデックス値
tmp_h := { 価値 :v => 0, 重さ :w => 0 } を宣言
if bit==1
tmp_h[:v] += S1[index][:v] // 荷物をナップサックに入れたときの価値を加算
tmp_h[:w] += S1[index][:w] // 荷物をナップサックに入れたときの重さを加算
end
if tmp_h[:w] < W // もし荷物の重さが上限を超えていないならば
tmp_a に tmp_h を追加
end
}
tmp_a := tmp_a を 価値の大きい順にソート
S2 := item[N/2～N] // 荷物の後半分を切り出し
ans_v := 0 // 答え
for (S2の個数でbit全探索) {
bit := 1 or 0
idx := S2のインデックス値
tmp_h := { 価値 :v => 0, 重さ :w => 0 } を宣言
if bit==1
tmp_h[:v] += S2[index][:v] // 荷物をナップサックに入れたときの価値を加算
tmp_h[:w] += S2[index][:w] // 荷物をナップサックに入れたときの重さを加算
end
if tmp_h[:w] < W // もし荷物の重さが上限を超えていないならば
x := { tmp_a を前から検索・その重さと tmp_h[:w] を加算してWを超えない最初のハッシュを取得 }
ans_v := ( x[:v] + tmp_h[:v] と ans_v を比べて大きいもの )
end
}
ans_v を出力する
