paizaラーニング レベルアップ問題集 新・Bランクレベルアップメニュー JavaScript 【全探索 2】コップの水

【全探索 2】コップの水 (paizaランク B 相当)

考え方

最適なプレイをしたとき、大きなコップに水を何 ml 入れることができるか。
小さなコップのすべての組み合わせを考える。
その中から、大きなコップからこぼれない範囲で最大量を求めればよい。

---

二進数で、小さなコップのすべての組み合わせを考えられる。
例えば、入力例1のN=3で考えてみると、以下の表のようになる。

10進数	2進数	2の何乗か
1	001	2^0
2	010	2^1
3	011
4	100	2^2
5	101
6	110
7	111
8	1000	2^3

2進数のところを見て、小さなコップ3個並んでいるのをイメージする。
大きなコップに、0は入れない、1は入れる、とすると、すべての組み合わせが考えられる。

これは、bit全探索という手法のようです。

解答例

考え方の通りに実装しました。
.toString(2)で2進数に変換して、N桁に揃え、順に１かどうか判定しています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//N 個の小さなコップ,容量が X ml の大きなコップ
const [N, X] = lines[0].split(" ").map(Number);
//w_1 ml, ..., w_N ml の水の入った N 個の小さなコップを用意する。
const w = lines.slice(1).map(Number);

let max = 0;//大きなコップに入る最大量

//二進法で考えます。入れるを1、入れないを0として、ビット探索します。
for (let i = 1; i < 2 ** N; i++) { //上記の考え方参照
  //１０進数iを2進数の0と1の列に変換する。
  let bi = i.toString(2);
  //N桁に揃える
  while (bi.length < N) {
    bi = "0" + bi;//0は前につける
  }
  
  
  let sum = 0;//ある組み合わせの水の合計量
  //2進数の0と1の列について先頭から見ていく
  for (let j = 0; j < N; j++) {
    //1は小さなコップの水を大きなコップに入れる、0は入れない
    if (bi[j] === "1") { 
      sum += w[j];
    }
  }
  
  if (sum <= X) { //大きなコップからあふれなかったら
    //最大更新
    max = Math.max(max, sum);
    if (max === X) break;//大きなコップギリギリになったら、これ以上はないので探索終わり
  }  
}
console.log(max);

ビット探索のところは、ビット演算子を用いると、以下のようにも書けます。
考え方は一緒ですが、(i >> j) & 1) === 1は、iの二進数を、>> jで順に右にずらしながら、& 1 === 1で一番右側が１かどうか判定しながら、探索しています。

//二進法で考えます。入れるを1、入れないを0として、ビット探索します。
for (let i = 1; i < 2 ** N; i++) {

  //bit全探索
  let sum = 0;//ある組み合わせの水の合計量
  for (let j = 0; j < N; j++) {
    if (((i >> j) & 1) === 1) { //ビット演算子を用いた
      sum += w[j];
    }
  }
  
  if (sum <= X) { //大きなコップからあふれなかったら
    //最大更新
    max = Math.max(max, sum);
    if (max === X) break;//大きなコップギリギリになったら、終わり
  }
  
}

ビット演算子を用いたところ(i >> j) & 1) === 1のイメージは以下の通り。
i >> j
１０進数iを2進数で考えて、j個だけ右にずらす。
例えば、10進数i=6を2進数で考えると0110で、
j=1個だけ右にずらすと0011になり、10進数の3になる。
j=2個だけ右にずらすと0001になり、10進数の1になる。

& 1 === 1は、(i >> j)の2進数の一番右が1かどうかを判定している。

よって、(i >> j) & 1) === 1は、(i >> j)で、ところてんのように１つずつ右側に押し出している2進数を、& 1 === 1でiの2進数の一番右の数を0か１か判定している。

110　一番右は1か
011　一番右は1か
001　一番右は1か

すなわち、iの2進数のすべての0と1について、1か判定している。

解答例 (C++の場合参考)

ビット探索を以下のようにしている。

tmpをビット探索する数とする。
tmpを２で割ったあまりが１か判定。これは、2進数で考えたとき、一番右の数が１か判定していることに相当する。
tmpを２で割って次を調べる。これは2進数でいうと、右に一つずらしていることに相当する。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//N 個の小さなコップ,容量が X ml の大きなコップ
const [N, X] = lines[0].split(" ").map(Number);
//w_1 ml, ..., w_N ml の水の入った N 個の小さなコップを用意する。
const w = lines.slice(1).map(Number);

let max = 0;

//二進法で考えます。入れるを1、入れないを0として、全探索します。
for (let i = 1; i < Math.pow(2, N); i++) {

  //bit全探索
  let sum = 0;//ある組み合わせの水の合計量
  let tmp = i;
  for (let j = 0; j < N; j++) {
    if (tmp % 2 === 1) { //tmpを2進数で考えた時、一番右が1か
      sum += w[j];
    }
    tmp /= 2;//tmpを2進数で考えた時、右に一つずらしている
  }
  
  if (sum <= X) { //大きなコップからあふれなかったら
    //最大更新
    max = Math.max(max, sum);
    if (max === X) break;//大きなコップギリギリになったら、終わり
  }
  
}
console.log(max);