関数で解けますか？・・・ナップサック問題解答例

　当初は総当たりの解答しか、用意していなかったんですが

ジョー３さんから、芸がないとのお叱りを受け急遽、別解を

用意しました。三四郎版は当初予定していたものと同じです。

エクセル版は循環参照を利用していますので

他のファイルを開かないで下さい。

三四郎版は圧縮しないと７７４KBですが、エクセル版は１６KBです。

receipt_sanshiro.lzhをダウンロード

Q4_kumapooh_Kaitei.lzhをダウンロード （Excel２００７　改訂版）

Q4_kumapooh_Kaitei_xls.lzhをダウンロード （Excel２０００－２００３改訂版）

※エクセル版はDec2Bin関数を使っています。Excel２００７ならば

そのまま動きますがExcel2000等ではアドイン「分析ツール」を

組み込む必要があります。

　「Excel２０００－２００３」用はエクセル２００７で保存し直しただけで

動作の検証はしていません(^^ゞ

******************************************************

エクセルの改訂版をアップしました。（2009/02/02）

Comments

[投稿情報: ジョー３]

ヤハリ、反復計算・・・・
へーーー出来るんですねーーー
上手なモンです。

で、ついでに、３０枚の領収証でも
出来るようにして欲しいなーー

それが出来たら、ＲＡＮＤ解法からは
手を引きたいぐらいですーー

[投稿情報: minmax]

さすがですね。
>ヤハリ、反復計算・・・・×２
反復計算をやろうと思ったのですが、時間と技術が足りませんでした。

DEC2BINはヒントをもらっていたので分かったのですが、５１１までしかやれないので、代わりに
TEXT(SUM(INT(MOD(ROW(A1),2^ROW($1:$10))/2^(ROW($1:$10)-1))*10^(ROW($1:$10)-1)),"0000000000")
（配列数式が前提です）
で1023まで出来るようにしてROW(A1)の部分を反復計算に置き換えてファイルサイズ縮小しようとしたのですが出来ませんでした。
結局255KBどまりでした。

[投稿情報: y sakuda]

くまプーさんのシート、チラッと見ましたが良く分からんｗ
で、さっき申し上げた385通りと言う話題のみ参加^^;
7777を超えるには、上の方から足し行っても、最低6個必要
10個全部使う必要はないので、最高9個の和となります。

6個の組み合わせ10C6　で210通り
7個の組み合わせ10C7　で120通り
8個の組み合わせ10C8　で45通り
9個の組み合わせ10C9　で10通り
合計385の組み合わせを試すだけで十分と言うことです。
実際には9個の組み合わせの最小が下から9個足した物でも9000円を越えますから無視しても良いはずです。

[投稿情報: y sakuda]

くまぷーさんの仕組みはなんとなく分かりました。
が・・・・
なんで、最初から1922円は使うことに決めちゃってるのかな？

[投稿情報: くまぷー]

>３０枚の領収証でも
出来るようにして欲しいなーー

やることは同じだから
できないことはないと思うけど
エクセルの１回の反復計算回数の上限は
約３２０００回だからやる気がしない・・・(^^ゞ

[投稿情報:]

>できないことはないと思うけど
>だからやる気がしない・・・(^^ゞ
そ、、、そこをなんとか、、、お師匠様。！！

やる気出してちょうだい！！

[投稿情報: くまぷー]

＞=TEXT(SUM(INT(MOD(ROW(A1),2^ROW($1:$10))/2^(ROW($1:$10)-1))*10^(ROW($1:$10)-1)),"0000000000")

いや～、よくこんな式を考えましたね～
流石です。

＞反復計算に置き換えて
ここまで出来ていれば出来たも同じですよ！！

[投稿情報: くまぷー]

＞6個の組み合わせ10C6　で210通り
＞7個の組み合わせ10C7　で120通り
＞8個の組み合わせ10C8　で45通り
＞9個の組み合わせ10C9　で10通り

なるほど、そういうことですか～

＞なんで、最初から1922円は使うことに決めちゃってるのかな？

Dec2Binの十進数の上限が511だから
１～９枚目の領収書の使用・不使用は
Dec2Binで賄えます。
しかし、１０枚目はダメなのでそこだけ
使用・不使用を別に検査しています。

・・・で初期状態で10枚目は赤くなって
いますが、Startするときっちり、10枚目も
検査します。
　数字を使わない領収書（例えば９６１円）と
交換するとちゃんと検査しているのが
わかると思います。

[投稿情報: くまぷー]

＞やる気出してちょうだい！！

いやいや・・・(^^ゞ

[投稿情報: minmax]

素朴な疑問、
サンプルでは２枚目のレシートは\1,766なのに
くまぷーさんの解答ファイルでは\1,776になっている？
単純なミスかな？
答えが合わなかったので気になっただけです。

[投稿情報: くまぷー]

＞単純なミスかな？

すみません、入力ミスです　m(__)m

[投稿情報: minmax]

あともう一つ
１０番目のレシートが７７７７円だったらそのレシート１枚だけでOKですよね？

[投稿情報: くまぷー]

＞１０番目のレシートが７７７７円だったらそのレシート１枚だけでOKですよね？

あっ、バグが見つかっちゃいましたね　(^^ゞ

A2の式が・・・
=IF(A1,IF(A2<511,A2+1,A2),0)
・・・なので、A2の初期値が1になってしまい
000000000の場合、つまり1枚目から9枚目までの
領収書を全て使わない場合が検査から
漏れていました。

スミマセンがA2の式を
=IF(A1,IF(A2<511,A2+1,A2),-1)
に変えて下さい　m(__)m

[投稿情報: くまぷー]

あ、でさらに反復計算回数を５１２以上に
設定し直して下さい。m(__)m

[投稿情報: くまぷー]

エクセルの改訂版をアップしました。