c# - 四舍五入数量与可用面额

Question

这不是基于单个值向上或向下舍入的常规舍入。
我想有一个函数，在这里我把数量作为整数传递，面额作为整数数组传递。
这个函数应该返回给我的是一个最接近的整数，可以通过传递的面额数组实现。
是否向上取整或向下取整将再次作为参数发送。
代码：

var amount = 61; // for. e.g.
int[] denoms = [20, 50]; // for. e.g.
bool roundUp = true;
amount = RoundAmount(amount, denoms, roundUp);

预期结果：
RoundAmount函数应该返回我通过denoms可以达到的最接近的值。
如果 roundUp = true，则返回值应为 70，因为 70 = 20+50
一个20秒音符和一个50秒音符可以得到 70的量。
如果 roundUp = false，它应该返回 60，因为 60 =
20+20+20和amount 60可以通过3个20秒的音符来实现
到目前为止我得到的是：
我只到了可以根据一个整数（而不是整数数组）上下取整的程度。

public int RoundAmount(int amount, int value, bool roundUp)
{
   if (roundUp)
      amount = amount - (amount % value) + value;
   else
      amount = amount - (amount % value)

   return amount;
}

编辑：
我有另一个递归函数来检查数量是否可以达到，
只有当数量无法实现时，才会调用 RoundAmount函数。
所以在我的例子中， amount = 70永远不会是输入，因为 70可以用可用的denom实现，在这种情况下我不会调用 RoundAmount。
解决方案：（感谢Maraca和Koray）
我很高兴它使用 long数字，尽管这不是最初的要求。

private static long RoundAmount_maraca(long a, long[] d, bool up)
{
    d = d.ToArray();
    Array.Sort(d);

    if (a < d[0])
        return up ? d[0] : 0;
    long count = 0;
    for (long i = 0; i < d.Length; i++)
    {
        if (d[i] == 0)
            continue;
        for (long j = i + 1; j < d.Length; j++)
            if (d[j] % d[i] == 0)
                d[j] = 0;
        if (d[i] > a && !up)
            break;
        d[count++] = d[i];
        if (d[i] > a)
            break;
    }
    if (count == 1)
        return (!up ? a : (a + d[0] - 1)) / d[0] * d[0];
    long gcd = euclid(d[1], d[0]);
    for (long i = 2; i < count && gcd > 1; i++)
        gcd = euclid(d[i], gcd);
    if (up)
        a = (a + gcd - 1) / gcd;
    else
        a /= gcd;
    for (long i = 0; i < count; i++)
    {
        d[i] /= gcd;
        if (a % d[i] == 0)
            return a * gcd;
    }
    var set = new HashSet<long>();
    set.Add(0);
    long last = 0;
    for (long n = d[0]; ; n++)
    {
        if (!up && n > a)
            return last * gcd;
        for (long i = 0; i < count && n - d[i] >= 0; i++)
        {
            if (set.Contains(n - d[i]))
            {
                if (n >= a)
                    return n * gcd;
                if ((a - n) % d[0] == 0)
                    return a * gcd;
                set.Add(n);
                last = n;
                break;
            }
        }
    }
}
private static long euclid(long a, long b)
{
    while (b != 0)
    {
        long h = a % b;
        a = b;
        b = h;
    }
    return a;
}

Answer 1

我假设您正在寻找一种性能较好的解决方案，其面额相对较小（例如，面额小于100）。而数量b和面额a可能相当大（例如小于10^6）。
升序排序并删除重复项。当舍入时，只保留小于或等于d[i]的值；当舍入时，只保留大于或等于d的最小值，并丢弃较大的值。
（可选）删除其他数字o（b^2）的倍数的所有数字。
计算面额的最大公约数。你可以用欧几里德算法从前两个数开始，然后计算结果的最大公约数和第三个数，依此类推。你当然可以一到就停下来。
将a除以a，像要对结果进行舍入一样进行舍入（使用整数除法，舍入：gcd，舍入：a）。
将所有面额除以gcd（a /= gcd）。现在所有面额的最大公约数是一个，因此保证Frobenius数存在（所有数量大于该数可以建立并且不需要舍入）。执行此操作时，还可以检查新值是否导致a = (a + gcd - 1) / gcd，如果是，则立即返回gcd。
为可以生成的值创建一个hashd[i] /= gcd。它比数组好，因为数组可能会浪费很多空间（记住frobenius数）。把零加到集合中。
为当前号码创建一个变量a % d[i] == 0，并用最小的名称初始化：a * gcd。
如果set可以用任何可用的面额构建，换句话说，n包含任何n = d[0]的面额，则继续下一步。否则，将n增加一个并重复此步骤，除非set并且您正在向下舍入，然后您可以立即返回可以生成的最后一个数字乘以n - d[i]。您还可以每次从n中删除n == a，因为将不再请求此值。
如果gcd返回n - d[b - 1]（只有在向上取整时才能为真，则向下取整将在步骤8中返回结果。已经）。否则，如果set返回n >= a。这种检查甚至比寻找frobenius数（可以建立n * gcd连续值的数）更好，它或多或少是等价的（(a - n) % d[0] == 0连续值意味着其中一个值与a * gcd模d[0] - 1之间的差必须为零），但返回速度更快。否则将d[0] - 1增加一个并继续执行步骤8。
一个d={4，6}和a=9999（或任何其他大奇数）的例子显示了该算法的优点。很容易看出奇数永远不会被建立，我们会用除了2以外的所有偶数填充整个集合。但是如果我们除以gcd，我们得到d={2，3}，aup=5000和adown=4999。{2，3}的frobenius数是1（唯一不能建立的数），因此在最多3（所有模都被覆盖的第一个数）步（而不是10000）之后，模将为零，我们将返回一个*gcd，它根据取整方向给出9998或10000，这是正确的结果。
这是包含测试的代码。我在我糟糕的笔记本上跑了6次，用了90秒、92秒、108秒、94秒、96秒和101秒（编辑：如果当前面额大于当前面额，则提前循环转义a将时间减半，平均约45秒），共有7200个随机圆（每个方向3600个圆）和不同面额的组合（范围2到100），dmax（范围100到10^6）和amax（范围10^4到10^6），（具体值请参见底部的代码）。我认为随机数生成和输出的时间可以忽略不计，因此在这个输入和给定的范围内，算法平均每秒循环大约160个数（编辑：见下面30倍的快速版本）。

public static final int round(int a, int[] d, boolean up) {
    d = d.clone(); // otherwise input gets changed
    Arrays.sort(d);
    if (a < d[0])
        return up ? d[0] : 0;
    int count = 0;
    for (int i = 0; i < d.length; i++) {
        if (d[i] == 0)
            continue;
        for (int j = i + 1; j < d.length; j++)
            if (d[j] % d[i] == 0)
                d[j] = 0;
        if (d[i] > a && !up)
            break;
        d[count++] = d[i];
        if (d[i] > a)
            break;
    }
    if (count == 1)
        return (!up ? a : (a + d[0] - 1)) / d[0] * d[0];
    int gcd = euclid(d[1], d[0]);
    for (int i = 2; i < count && gcd > 1; i++)
        gcd = euclid(d[i], gcd);
    if (up)
        a = (a + gcd - 1) / gcd;
    else
        a /= gcd;
    for (int i = 0; i < count; i++) {
        d[i] /= gcd;
        if (a % d[i] == 0)
            return a * gcd;
    }
    Set<Integer> set = new HashSet<>();
    set.add(0);
    int last = 0;
    for (int n = d[0];; n++) {
        if (!up && n > a)
            return last * gcd;
        for (int i = 0; i < count && n - d[i] >= 0; i++) {
            if (set.contains(n - d[i])) {
                if (n >= a)
                    return n * gcd;
                if ((a - n) % d[0] == 0)
                    return a * gcd;
                set.add(n);
                last = n;
                break;
            }
        }
    }
}

public static final int euclid(int a, int b) {
    while (b != 0) {
        int h = a % b;
        a = b;
        b = h;
    }
    return a;
}

public static final int REPEAT = 100;
public static final int[] D_COUNT = {2, 5, 10, 20, 50, 100};
public static final int[] D_MAX = {100, 10000, 1000000};
public static final int[] A_MAX = {10000, 1000000};

public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Random r = new Random();
    for (int i = 0; i < REPEAT; i++) {
        for (int j = 0; j < D_COUNT.length; j++) {
            for (int k = 0; k < D_MAX.length; k++) {
                for (int l = 0; l < A_MAX.length; l++) {
                    int[] d = new int[D_COUNT[j]];
                    for (int m = 0; m < d.length; m++)
                        d[m] = r.nextInt(D_MAX[k]);
                    int a = r.nextInt(A_MAX[l]);
                    System.out.println(round(a, d, false));
                    System.out.println(round(a, d, true));
                }
            }
        }
    }
    System.out.println((System.currentTimeMillis() - start) / 1000 + " seconds");
}

事实证明，@koray的edit 7对于给定的输入大约快三倍（只有对于非常大的gcd，我上面的算法才快）。为了得到最终的算法，我用@koray替换了算法中的动态编程部分（做了一些改进）。它的运行速度大约是edit 7的10倍，比上面的算法快30倍。平均每秒大约有5000个圆（非常粗略的估计）。

private static int round(int a, int[] d, boolean up) {
    d = d.clone();
    Arrays.sort(d);
    if (a < d[0])
        return up ? d[0] : 0;
    int count = 0;
    for (int i = 0; i < d.length; i++) {
        if (d[i] == 0)
            continue;
        if (a % d[i] == 0)
            return a;
        for (int j = i + 1; j < d.length; j++)
            if (d[j] > 0 && d[j] % d[i] == 0)
                d[j] = 0;
        if (d[i] > a && !up)
            break;
        d[count++] = d[i];
        if (d[i] > a)
            break;
    }
    if (count == 1)
        return (!up ? a : (a + d[0] - 1)) / d[0] * d[0];
    int gcd = euclid(d[1], d[0]);
    for (int i = 2; i < count && gcd > 1; i++)
        gcd = euclid(d[i], gcd);
    if (gcd > 1) {
        if (up)
            a = (a + gcd - 1) / gcd;
        else
            a /= gcd;
        for (int i = 0; i < count; i++) {
            d[i] /= gcd;
            if (a % d[i] == 0)
                return a * gcd;
        }
    }
    int best = !up ? d[count - 1] : ((a + d[0] - 1) / d[0] * d[0]);
    if (d[count - 1] > a) {
        if (d[count - 1] < best)
            best = d[count - 1];
        count--;
    }
    Stack<Integer> st = new Stack<Integer>();
    BitSet ba = new BitSet(a + 1);
    for (int i = 0; i < count; i++) {
        ba.set(d[i]);
        st.push(d[i]);
    }
    while (st.size() > 0) {
        int v1 = st.pop();
        for (int i = 0; i < count; i++) {
            int val = v1 + d[i];
            if (val <= a && !ba.get(val)) {
                if ((a - val) % d[0] == 0)
                    return a * gcd;
                ba.set(val, true);
                st.push(val);
                if (!up && val > best)
                    best = val;
            } else if (val > a) {
                if (up && val < best)
                    best = val;
                break;
            }
        }
    }
    return best * gcd;
}