（Gスプレッドシート）ナップザック問題を関数で解く（総当たり法）

　Googleスプレッドシートで関数によりナップザック問題（ナップサック問題）を解く例についてです。
　なお、ここでのナップザック問題とは1つのアイテムについて1個または0個を選択する0-1ナップザック問題です。
　1セルでの解決にこだわったせいでかなり長い式になっています。

• ナップザック問題のような問題も関数で扱うことができます。

手順

　B,C列にアイテムの価値と重量の組み合わせが記録されています。また、C2にはアイテム数が、C3には上限重量が記録されています。
　上限重量を超えない範囲で価値が最大になるようなアイテムの組み合わせを選ぶものとします。

　F4セルに次のように入力します。
　

=TRANSPOSE(QUERY(MMULT(ARRAYFORMULA(SPLIT(REGEXREPLACE(BASE(SEQUENCE(2^B3-1),2,B3),"","_"),"_")),{OFFSET(B6,0,0,B3,2),MUNIT(B3)}),"WHERE Col2<="&C3&" ORDER BY Col1 DESC,Col2"))

SEQUENCE関数で0,0,0,…,1から1,1,1,…,1までの組み合わせを生成し、{価値列(B),重量列(C),単位行列}との掛け算により総価値・総重量と選択の組み合わせ（結果表示用）を得ます。次にQUERY関数により重量オーバーとなる組み合わせの削除と並べ替えを行い、最後にTRANSPOSE関数で表にフィットするよう転置します。
　

　実行結果です。
　1,4,7番目のアイテムを選択することで（F6,F9,F12の値が1）価値が385となり（F4の値）、このときの重量は97となります（F5の値）。これが最も価値の高い組み合わせで、あとは価値が高い順に答えが右に並んでいきます。同価値の組み合わせが複数ある場合、総重量の軽い方が左に来ます。
　なお、B6以降に記録されているアイテム数がB3の数値より少ないとエラーになります。逆に多いと下の方のアイテムが結果に反映されません。
　総当たりのためアイテムが増えると急激に重くなります。また、すべての組み合わせを結果を表示する列数が足りなくなります。表示に支障が出る場合はQUERY関数のLIMIT句などで調整してください。

　最後に余談ですがARRAYFORMULA関数の直後のSPLITとREGEXREPLACE関数の部分（0,0,0,…,1から1,1,1,…,1を配列に分割している）はMIDとSEQUENCE関数と用いると若干短くできます。