From: "Matt Timmermans" Newsgroups: sci.math.num-analysis,comp.theory Subject: Re: Algorithm for finding values adding up to target value Date: Fri, 10 Jul 1998 13:24:45 -0400 Neil Negandhi wrote in message <35a622e9.2289968@news.interlog.com>... >I have a series of dollar values, mostly positive, typically ranging >from 50 to 1,000. The negative values typically range from -500 to >-5,000. The series will usually consist of 20 to 1000 values. The >user needs to be able to enter a target value and have the dollar >values which add up to this target selected for them. Realizing that >a perfect match is not always possible, the user will also enter the >acceptable variance. This is the knapsack problem, and it is NP complete. However, there is a tractable solution if your dollar amounts have a "large" greatest common divisor. With the numbers you've given, it would probably suffice if they were all an integral number of dollars (no cents). In that case, you simply keep an index of total amounts you could possibly reach. For each reachable amount, remember the its "cost" and the "best" previous amount. If you wanted the answer with the fewest numbers from the series, for example, a total's cost would be the number of numbers you have to add to get that total. The index starts containing only 0->(0,0) for total->(cost,prev). Now just run through your series in order. For each amount in the series, add it to the each entry in the index to find another possible total amount. If the possible amount doesn't exist in the index, add it. If it does, but the possible amount has lower cost than the current entry for that amount, replace the current entry. At the end, you have an index of all amounts you can reach, and the cost for each such amount. For any reachable amount, you can walk back through the prev field to find the best subsequence of your list.