Namaran

Code daily. Without assist.

2026-11-09

best_load.cpp

#include <print>

int main() {
    int w[] = {4, 6, 9};
    int best = 0;
    for (int mask = 0; mask < (1 << 3); ++mask) {
        int sum = 0;
        for (int i = 0; i < 3; ++i) {
            if ((mask & (1 << i)) == 1) {
                sum += w[i];
            }
        }
        if (sum <= 12 && sum > best) {
            best = sum;
        }
    }
    std::println("{}", best);
}

重さ 4、6、9 の荷物から何個かを選び、合計が12以下になる組のうち最も重い合計を表示するつもりのプログラムです。3個の選び方をすべて試すと、本来は4と6を選んだ 10 が出るはずが、いまは 4 が出ます。

Answer

Wrong

            if ((mask & (1 << i)) == 1) {
                sum += w[i];
            }
        }
        if (sum <= 12 && sum > best) {

mask & (1 << i) は、mask の i ビット目だけを残した値です。このビットが立っていれば結果は 1 << i(i が0なら1、1なら2、2なら4)になり、立っていなければ0になります。1と等しくなるのは i が0のときだけなので、この条件は w[1] と w[2] を一度も選びません。どの mask でも sum は0か w[0] の4にしかならず、12以下で最も重い合計として4が残ります。

Right

            if ((mask & (1 << i)) != 0) {
                sum += w[i];
            }
        }
        if (sum <= 12 && sum > best) {

ビットが立っているかどうかは、取り出した値が0でないかで判定します。!= 0 なら、i が何であっても、立っているビットに対応する荷物が選ばれます。合計は mask の順に0、4、6、10、9、13、15、19となり、12以下で最も重いのは4と6の10です。((mask >> i) & 1) == 1 のように、先に i ビット目を一番下へずらしてから1と比べる書き方でも同じ結果になります。