【TypeScript】Bit演算を使ってありえる通りを全探索する

概要

ありえる通りの数を全部試してみる、というアルゴリズムです。

Bit演算なんてあんまり使う機会無いですよね。でも実はこんな便利なことができます。

例

例えば、AtCoderのこの問題について考えます。
https://atcoder.jp/contests/abc032/tasks/abc032_d

n個の荷物があります。
それぞれに価値と重さが決まっています。
ナップサックに入れられる重さには限りがあります。
最大でどれだけの価値をナップサックに入れられるでしょうか？

普通に考えて、できるだけ軽くて価値があるものから順番に入れていけば良さそうですよね。
でも、色々エッジケースもあって大変そうです。
nが小さければ全部試してみる方が楽そうです。
計算量は全体で2のn乗です。
大体の端末でnが10~20以内であれば十分な速度で動きます。

コード

const n = 3;
const w = 10;

interface Item {
  value: number;
  weight: number;
}

const items: Item[] = [
  { value: 15, weight: 9 },
  { value: 10, weight: 6 },
  { value: 6, weight: 4 },
];

function main() {
  let ans = 0;
  for (let i = 0; i < (1 << n); i++) {
    let valueSum = 0,
      weightSum = 0;
    for (let j = 0; j < n; j++) {
      if (!((i >> j) & 1)) continue;
      valueSum += items[j].value;
      weightSum += items[j].weight;
    }
    if (weightSum > w) continue;
    ans = Math.max(ans, valueSum);
  }
  console.log(ans);
}

main();

解説

この場合iは

000
001
010
...

と全通りを取ります。

if (!((i >> j) & 1))あたりがよく分らんと思います。
ここは要するにiのときにjがONかOFFかを判定しています。