bit全探索

例題： ある整数の集合が与えられたとき、その部分集合の中である値X以上となるものの中で最小の総和を求める問題。

例えば、集合が {1, 2, 5, 10} で、X = 10 だとすると、部分集合 {10} や {5, 5} や {2, 2, 5} などが考えられ、その中で総和が最小となる部分集合は {10} で、総和は 10 となります。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    // 要素の数
    int n = 4;

    // 要素
    vector<int> a = {1, 2, 5, 10};

    // 目標となる値
    int X = 10;

    // 最小の総和を表す変数（最初は最大値に設定）
    int min_sum = INT_MAX;

    // ビット全探索：0から2^nまでループ
    for (int bit = 0; bit < (1<<n); ++bit) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            // i番目の要素を選ぶかどうか
            if (bit & (1<<i)) { // i番目のフラグが立っているならば
                sum += a[i]; // 総和に加算
            }
        }
        // 総和がX以上かつ最小ならば更新
        if (sum >= X) {
            min_sum = min(min_sum, sum);
        }
    }

    // 最小の総和を出力
    cout << "Minimum sum >= " << X << " : " << min_sum << endl;

    return 0;
}