Efficient implementations of two variant subset sum problems
PeiZong Lee, Fang‐Yu Huang, Chorng-Yuan Huang, Hwann-Tzong Chen · 1996
This paper is concerned with designing efficient algorithms to process the appraisal books, which are used to estimate the amount of money lost due to a fire, in the Bank of Taiwan.First, we propose heuristic algorithms to pack appraisal books daily into bundles in the units of 1,000,000 dollars, 500,000 dollars, and 100,000 dollars.Second, we present efficient algorithms to take out certain appraisal books so that the amount of the remaining accumulated appraisal books is a multiple of one thousand dollars.We also introduce a software tool which integrates the functions of processing appraisal books.Experimental studies show that the software tool is very helpful for the clerks. lutfod uctiouThis paper is concerned with designing efficient algorithms which will allow us to process the appraisal books which are used to estimate the amount of money lost due to a fire.(These books are stored in the Bank of Taiwan's head office.)This process involves two variant subset sum problems. Appreiael Books ofl3ulut Paper MoneyWe first illustrate whence appraisal books of burnt paper money come.Burnt paper money means that paper money was burnt due to an accidental fire.In order to reduce the victim's losses, the victim can bring the ashes of the burnt paper money to a branch of the Investigation Bureau.After three weeks, the victim can get an appraisal book which indicates how much paper money this victim lost.Then, this victim can be reimbursed the same amount of money indicated in the appraisal book from any branch of the Bank of Taiwan.Therefore, from the Bank's point of view, appraisal books of burnt paper money are money although they cannot be used as hard currency.