ビット全探索の考え方

今回の問題

全探索に関する問題です。

＞1 〜 N 個のアイテムのうち、いくつかを選んで合計の水量が X 以下になるように組み合わせを選ぶ。最適な水量を求めなさい。

このような問題では、全ての選択肢を試すために「ビット全探索」を使うことができます。

ビット全探索とは？

ビット全探索とは、ビット演算を利用して、与えられた集合の全ての部分集合を効率よく探索する方法です。

N 個の要素の組み合わせを、2 の N 乗通り（全ての部分集合）をビット列で表現します。
各ビットが 1 であればその要素を選び、0 であればその要素を選ばないという形です。
具体的な例
例えば、次のように 3 個のアイテム（コップ）があるとします：

水量: [3, 5, 7] (ml)

1 番目のコップを選ぶ場合: 1 番目のビットが 1。
2 番目のコップを選ぶ場合: 2 番目のビットが 1。
1 番目と 2 番目のコップを選ぶ場合: 1 番目と 2 番目のビットが 1。
これらの組み合わせをビット列で表現し、全ての可能な選択肢を探索します。

ビット全探索を使うメリット

ビット全探索を使用することで、次のような利点があります。

全ての組み合わせを簡単に列挙できる。
比較的少ないコードで解くことができる。
条件に基づいて簡単に組み合わせをチェックできる。

実装例

以下に、簡単なビット全探索の例を示します。この例では、与えられたコップから水量を最大化する組み合わせを選びます。水量が X 以下になる組み合わせを探索します。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        // 自分の得意な言語で
        // Let's チャレンジ！！
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();//小さいコップの個数
        int X = sc.nextInt();//大きいコップの容量
        int[]w = new int[N];//小さいコップ
        for(int i = 0; i < N;i++){
            w[i] = sc.nextInt();
        }
        int maxSum = 0;//合計値のうち最大
        
        //小さいコップのすべての組み合わせ分ループ
        for(int bit = 0; bit < (1 << N);bit ++){
            int sum = 0;
            for(int i = 0; i < N;i++){
                //今回のbitで選ばれたコップの水を加算
                if((bit & (1 << i)) > 0){
                    sum += w[i];
                }
            }
            
            // 合計水量が大きいコップの容量以下の場合、最大値を更新
            if(sum <= X){
            maxSum = Math.max(sum,maxSum);
            }
        }
        
        System.out.println(maxSum);
    }
}

コードの解説
外側の for 文
for (int bit = 0; bit < (1 << N); bit++) は、2 の N 乗通りのビット列を使って全ての組み合わせを列挙しています。ここでの bit は、N 個の要素が選ばれているかどうかを示すビット列です。

内側の for 文
各 bit に対して、各要素が選ばれているか（ビットが 1 か）を判定するために、(bit & (1 << i)) > 0 の条件でビット演算を行い、選ばれていればそのコップの水量 w[i] を加算します。

最大水量の更新
合計水量 sum が大きなコップの容量 X 以下であれば、その水量が最大値より大きければ更新します。

さいごに

今回の探索方法は、かなりいろいろな問題に応用できそうと感じました。
まだまだ知らないことだらけですが引き続き頑張ります!