Namaran

Code daily. Without assist.

2026-08-26

count_fits.rs

fn count_fits(w: &[u32], cap: u32) -> usize {
    (0u8..1 << w.len())
        .filter(|m| {
            let s: u32 = (0..w.len())
                .filter(|i| m >> i & 1 == 1)
                .map(|i| w[i])
                .sum();
            s <= cap
        })
        .count()
}

fn main() {
    let w = [1, 1, 1, 1, 1, 1, 1, 1];
    println!("{}", count_fits(&w, 1));
}

重さを並べた w から、重さの合計が cap 以下になる選び方の数を、何も選ばない選び方も含めて数えるつもりの count_fits です。重さ1の品物8個と cap = 1 を渡すと 9 と出力するはずが、いまは何も出力せずに attempt to shift left with overflow でパニックします。

Answer

Wrong

(0u8..1 << w.len())

範囲 a..b の両端は同じ型なので、始まりを 0u8 と書くと、終わりの 1 << w.len() も u8 で計算されます。w が8要素なら、これは 1u8 << 8 です。u8 は8ビットしかないので、8ビット以上ずらすシフトはオーバーフローとして扱われ、デバッグビルドではここでパニックします1。選び方を1つも数えないうちに止まるので、何も出力されません。

8要素の選び方を表す mask の値は0から255までで、どれも u8 に入ります。入らないのは、範囲の終わりに置いた256だけです。a..b は b を含まない範囲なので、最後の値255を回すには、その1つ先の256を書ける型が要ります。7要素までなら終わりは128以下で、このコードは正しく数えます。

Right

(0u16..1 << w.len())

マスクを u16 にすると、1u16 << 8 は256になり、mask は0から255までの256通りを回ります。重さ1の品物8個で合計が1以下になるのは、何も選ばない1通りと、1個だけ選ぶ8通りなので、9 が出力されます。u16 で扱えるのは15要素までなので、要素数に上限がないなら usize にします。

  1. リリースビルドでは整数オーバーフローの検査が外れ、シフトする量は型のビット数で割った余りになります。1u8 << 8 は 1u8 << 0 の1になり、パニックせずに mask が0の1通りだけを数えて 1 を返します。