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

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

https://paiza.jp/works/mondai/b_rank_new_level_up_problems/b_rank_new_level_up_problems__a_cup_of_water

# 考え方
最適なプレイをしたとき、大きなコップに水を何 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桁に揃え、順に１かどうか判定しています。
```javascript
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`で一番右側が１かどうか判定しながら、探索しています。
```javascript
//二進法で考えます。入れるを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進数でいうと、右に一つずらしていることに相当する。

```javascript
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);
```