计算所需的最少笔记数 [英] calculate minimum amount of notes needed

问题描述

我正在尝试编写一种算法，计算出达到一个值所需的最少数量的纸币"或货币.

最明显的方法就是说:

I am trying to write an algorithm that calculates the minimum number of "notes", or currency needed to get to a value.

The most obvious way is to just say:

var notes = [];
while (val != 0) {
    //loop through array of possible notes
    for (note in noteArray) {
        if (note >= val) {
           notes.push(note);
           val -= note;
        }    
    }
}

这项工作100％有效，除了现在我在移动设备上进行操作外，在得出结果之前有明显的滞后.有没有更快的算法可以实现这一目标?

我当时正在考虑在其中实现二进制印章，然后看看它是否有所作为.

预先感谢，
Dom

This works 100%, except that now I am doing it on a mobile device, it has a noticeable lag before it draws the result. Is there a quicker algorithm out there for achieving this?

I was thinking about implementing a binary chop into it and seeing if it made a difference.

Thanks in advance,
Dom

推荐答案

假设您的音符数组以有序的最大顺序排列，我将简单地依次将值除以每个音符值:引号是要删除的那些音符的数量问题，其余部分将传递到下一个面额.

因此，如果您的值是123，而笔记是10、5和1:

Assuming that your note array in ordered largest first, I would simply divide the value by each note value in turn: the quotent is the number of those notes to issue, the remainder gets passed down to the next note denomination.

So if your value is 123 and your notes are 10, 5, and 1:

123 / 10: Q == 12, R == 3  (12 x 10 notes)
  3 /  5: Q ==  0, R == 3  (no 5 notes)
  3 /  1: Q ==  3, R == 0  (3 x 1 notes)

只需一个循环.

对于真实的货币和笔记:它们的值是设计这种方式时，您可以使用较低价值的票据获得下一个较高票据的价值，因此在这种情况下，解决方案1是最佳的.但是，对于音符值的任何组合而言，并非总是如此.考虑只想使用7和3的注释来获得值9的情况.

该算法处理所有情况下的音符值和最终值；
这只是一个伪代码.
假设您的笔记是按从高到低的顺序排列的.

resolve(v-值，ind-当前音符值索引){
如果(v == 0)解决方案
如果(ind == max_ind)达到最低注释，则该分支中没有解决方案
整数mcn = v％Notes [ind]; //当前笔记的最大数量
for(i = mcn to 0){
使用i有价票据Notes [ind]:v- = i * Notes [ind]

检查解决方案是否存在:solve(v，ind + 1)

"unuse"(不使用)我的有价票据Notes [ind]:v + = i * Notes [ind]
}
}

希望这可以帮助.如果您有任何疑问，请随时提问.

For real life currencies and notes: their values are designed in such a way that you can get the value of the next higher note using lower value notes so Solution 1 is the best one in this case. It is not always the case however for any combination of note values. Consider the case where you want to get value 9 using notes only of 7 and 3.

This algorithm handles all cases of note values and final value;
It''s just a pseudocode.
Assuming your notes are ordered from highest to lowest value.

solve( v - value, ind - current note value index) {
if (v==0) SOLUTION FOUND
if (ind == max_ind) LOWEST NOTE REACHED, NO SOLUTION IN THAT BRANCH OF THE RECURSION
integer mcn = v % Notes[ind]; // max number of current notes
for (i = mcn to 0) {
use i notes of value Notes[ind]: v-=i*Notes[ind]

check if solution exist: solve(v,ind+1)

"unuse" i notes of value Notes[ind]: v+=i*Notes[ind]
}
}

Hope this helps. If you have any questions feel free to ask.

这篇关于计算所需的最少笔记数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！