Path: ccsf.homeunix.org!CALA-MUZIK!news.media.kyoto-u.ac.jp!ns.4bn.ne.jp!news
From: Yoshitaka Ikeda <ikeda@4bn.ne.jp>
Newsgroups: fj.sci.math
Subject: =?iso-2022-jp?b?UmU6IBskQkFIJF85ZyRvJDsbKEI=?=
Date: 25 Sep 2006 09:39:28 +0900
Organization: Yonbetsu Netzwerk
Lines: 45
Sender: ikeda@4bn.ne.jp
Message-ID: <86u02weq4f.fsf@bsd2.4bn.ne.jp>
References: <ef6106$lee$1@news-wst.ocn.ad.jp>
NNTP-Posting-Host: kaneko20.ee.noda.sut.ac.jp
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-2022-jp
Content-Transfer-Encoding: 8bit
X-Trace: caraway.media.kyoto-u.ac.jp 1159154883 9253 133.31.107.241 (25 Sep 2006 03:28:03 GMT)
X-Complaints-To: news@news.media.kyoto-u.ac.jp
NNTP-Posting-Date: Mon, 25 Sep 2006 03:28:03 +0000 (UTC)
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3
Xref: ccsf.homeunix.org fj.sci.math:2079

"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