ビット全探索

ビット演算を活用して効率的に全ての部分集合を探索する重要な技法を学ぼう

O(2^n)

時間計算量

O(n)

空間計算量

中級

難易度

その他

カテゴリ

🔧 実行設定

操作:

subsetSum

配列:

[3, 1, 4, 2, 5]

目標値:

配列（カンマ区切り）

目標値（部分集合和用）

ナップサック用設定

💡 推奨操作

🔢

アルゴリズムを実行してください

左側の設定パネルから操作を選択し、「アルゴリズム実行」ボタンを押してください

💻 実装例（JavaScript）

// 全部分集合の生成
function allSubsets(arr) {
    const n = arr.length;
    const result = [];
    
    // 0から2^n-1まで全てのビットパターンを試す
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        
        for (let i = 0; i < n; i++) {
            // i番目のビットが立っているかチェック
            if ((mask >> i) & 1) {
                subset.push(arr[i]);
            }
        }
        
        result.push(subset);
    }
    
    return result;
}

// 部分集合和問題
function subsetSum(arr, target) {
    const n = arr.length;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        let sum = 0;
        const subset = [];
        
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                sum += arr[i];
                subset.push(arr[i]);
            }
        }
        
        if (sum === target) {
            return subset; // 解が見つかった
        }
    }
    
    return null; // 解なし
}

// ナップサック問題（小規模）
function knapsack(weights, values, capacity) {
    const n = weights.length;
    let maxValue = 0;
    let bestSubset = [];
    
    for (let mask = 0; mask < (1 << n); mask++) {
        let totalWeight = 0;
        let totalValue = 0;
        const subset = [];
        
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                totalWeight += weights[i];
                totalValue += values[i];
                subset.push(i);
            }
        }
        
        if (totalWeight <= capacity && totalValue > maxValue) {
            maxValue = totalValue;
            bestSubset = subset;
        }
    }
    
    return { value: maxValue, items: bestSubset };
}

// 使用例
const arr = [1, 2, 3];
console.log(allSubsets(arr)); // [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
console.log(subsetSum([1, 3, 5, 7], 8)); // [1, 7] or [3, 5]

const weights = [2, 1, 3];
const values = [12, 10, 20];
console.log(knapsack(weights, values, 5)); // {value: 22, items: [0, 1]}

🔧 実行設定

💡 推奨操作

アルゴリズムを実行してください

ビット全探索とは？

💻 実装例（JavaScript）