什么是良好的非递归算法来决定是否在传递量相加可以从一组数字来建？ [英] What is a good non-recursive algorithm for deciding whether a passed in amount can be built additively from a set of numbers?

问题描述

什么是非递归算法来决定是否通过的量可以从一组数字相加建成。
就我而言，我确定是否一定货币金额（如$ 40），可以通过添加一组账单的某种组合来满足（如$ 5，$ 10和$ 20个票据）。这是一个简单的例子，但该算法需要为任何货币集工作（某些货币使用时髦纸币金额和一些纸币可能不提供在给定的时间）。
因此，$ 50可遇到一组（$ 20和$ 30），但不能见了一组（$ 20和$ 40）。非递归的要求是由于目标code基正在为的SQL Server 2000 ，其中递归的支持是有限的。照片 另外，这是支持多币种环境下，票据可能改变设定（想了外币兑换取款为例）。

What is a non recursive algorithm for deciding whether a passed in amount can be built additively from a set of numbers.
In my case I'm determining whether a certain currency amount (such as $40) can be met by adding up some combination of a set of bills (such as $5, $10 and $20 bills). That is a simple example, but the algorithm needs to work for any currency set (some currencies use funky bill amounts and some bills may not be available at a given time).
So $50 can be met with a set of ($20 and $30), but cannot be met with a set of ($20 and $40). The non-recursive requirement is due to the target code base being for SQL Server 2000 where the support of recursion is limited.
In addition this is for supporting a multi currency environment where the set of bills available may change (think a foreign currency exchange teller for example).

推荐答案

如果你把每个面额作为一个基n个，其中n是音符，你将需要最多的一个点，那么你就可以增加通过数，直到你已经用尽的问题空间，或找到了解决办法。

If you treat each denomination as a point on a base-n number, where n is the maximum number of notes you would need, then you can increment through that number until you've exhausted the problem space or found a solution.

笔记，你将需要数最多为您所需要的最小单位记分总。

The maximum number of notes you would need is the Total you require divided by the lowest denomination note.

这是一个强力回应的问题，但它肯定会工作。

It's a brute force response to the problem, but it'll definitely work.

下面是一些对 - code。我可能遍布我的栅栏柱的地方，它是如此没有优化是荒谬的，但它应该工作。我认为这个想法是正确的呢。

Here's some p-code. I'm probably all over the place with my fence posts, and it's so unoptimized to be ridiculous, but it should work. I think the idea's right anyway.

Denominations = [10,20,50,100]
Required = 570

Denominations = sort(Denominations)
iBase = integer (Required / Denominations[1])

BumpList = array [Denominations.count]
BumpList.Clear

repeat 
    iTotal = 0 
    for iAdd = 1 to Bumplist.size
        iTotal = iTotal + bumplist [iAdd] * Denominations[iAdd]
    loop
    if iTotal = Required then exit true

    //this bit should be like a mileometer. 
    //We add 1 to each wheel, and trip over to the next wheel when it gets to iBase
    finished = true
    for iPos from bumplist.last to bumplist.first 
        if bumplist[iPos] = (iBase-1) then bumplist[iPos] = 0 
        else begin
            finished = false
            bumplist[iPos] = bumplist[iPos]+1
            exit for
        end
     loop 
until (finished)

exit false

这篇关于什么是良好的非递归算法来决定是否在传递量相加可以从一组数字来建？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！