"ocn" <spny9ar9@tiara.ocn.ne.jp> writes:

> きょうぐろです。
> 
> つぎのような問題はどう解決したらいいでしょうか？
> 
> 合計金額のみ記された請求書が毎日届くのですが、
> 内訳が付いていません。
> 事務のおばさんは個別明細伝票を請求書の金額に
> なるようあれこれ組み合わせるのに苦労しているので
> 簡単なプログラムをつくってあげたいと思います。
> (fortran)
> 
> たとえばある日の請求書が５００円で、未処理の
> 個別伝票が５０円、１００円、１５０円、２００円、３００円、
> ４００円残っている場合、
> 
> １）１００円、４００円
> ２）５０円、１５０円、３００円
> ３）５０円、１００円、１５０円、２００円
> 
> のような組み合わせで個別伝票をまとめて請求書に
> 添付し処理すればいいわけです。
> 
> もっともスマートなアルゴリズムはどんなものがあるでしょうか。
> 個別伝票の枚数は有限ですが、不定（せいぜい２０枚程度）
> です。総当たりする場合でも最小の回数にするには？

ナップサック問題じゃないのかなぁ。と思ったのですが、
高いものからつめていって、矛盾したところでバックトラックする
って処理でできませんか。

400,300,200,150,50

400
400+300 ×
400+200 ×
400+100 OK

こんな感じで。
総当りする必要は多分無いと思います。平均回数も最悪回数も評価していませんが。
-- 
I LOVE SNOOPY!  でつ
Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp
My Honeypot: honey@4bn.ne.jp  <-don't send this address