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