Rounding size with available set of names
It is not regular rounding and rounds up or down based on a single value. I would like to have a function where I pass the sum as an integer and the denominations as an integer array. What this function will return to me is the closest integer value reached with the passed array of bills. Whether rounding up or down will be sent again as a parameter.
Code:
var amount = 61; // for. e.g.
int[] denoms = [20, 50]; // for. e.g.
bool roundUp = true;
amount = RoundAmount(amount, denoms, roundUp);
Expected Result:
Function RoundAmount
should return me the closest possible amount reachable with the characters I passed.
- If
roundUp = true
, the return value should be70
, because70 = 20+50
both the sum70
can be reached in one note 20 s and one note 50 s. - If
roundUp = false
, he had to return60
, because the60 = 20+20+20
sum60
can be reached by three notes 20 seconds
What I got so far:
I was only achieved to the point where I was able to work around the sum up or down based on a single integer (not an array of integers)
public int RoundAmount(int amount, int value, bool roundUp)
{
if (roundUp)
amount = amount - (amount % value) + value;
else
amount = amount - (amount % value)
return amount;
}
Edit:
I have another recursive function that checks if the amount is reachable or not, Only if the amount is not reachable, the function is called RoundAmount
.
So, in my example, it amount = 70
will never be an input as it is 70
reachable by the available values, and I will not call RoundAmount
in this case.
Solution: (thanks to Marak and Korah)
I'm glad I worked with the numbers long
, although this was not an original requirement.
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;
}
source to share
I assume you are looking for a solution for artists with relatively few titles b
(e.g. less than 100 titles). Although the amount a
and denominations d[i]
can be quite large (for example, less than 10 ^ 6).
-
Sort
d
ascending and remove duplicates. When rounding, keep values less than or equala
, and when rounding, keep only the smallest value greater than or equal toa
and discard the larger. -
(Optional) remove all numbers that are multiples of some O (b ^ 2).
-
Calculate the greatest common divisor of
gcd
items. You can use Euclid's algorithm by starting with the first two numbers, then calculating the greatest common divisor of the result and the third, and so on. Of course, you can stop as soon as you reach one. -
Divide
a
bygcd
, round up as you want to round the result (using integer division, round down:,a /= gcd
round off:)a = (a + gcd - 1) / gcd
. -
Divide all titles by
gcd
(d[i] /= gcd
). Now the greatest common divisor of all names is one, and therefore it is guaranteed that the Frobenius number exists (all amounts exceeding this number can be constructed and do not require rounding). That being said, you can also check if the new value casts toa % d[i] == 0
and returns immediatelya * gcd
if it does. -
Create a hash
set
for the values that can be plotted. It is better than an array because an array is potentially a waste of space (remember Frobenius's number). Add zero to the set. -
Create a variable
n
for the current numbers, initialize the lowest denomination:n = d[0]
. -
If it
n
can be built with any of the available merits, in other words,set
contains any of the valuesn - d[i]
, then proceed to the next step. Otherwise, increasen
by one and repeat this step ifn == a
you round down too, after which you can immediately return the last number that can be built multiplied bygcd
. You can also removen - d[b - 1]
fromset
each time, because that value is no longer asked for. -
If
n >= a
returnn * gcd
(can only be true when rounding, rounding will return the result in step 8.) Otherwise, if it(a - n) % d[0] == 0
returnsa * gcd
. This check is even better than looking for a Frobenius number (a number after whichd[0] - 1
you can build consecutive values), it is more or less equivalent (d[0] - 1
consecutive values mean the difference between one of them anda
modulod[0]
should be zero), but it can return much faster. Else is incrementedn
by one and continue from step 8.
The example with d = {4, 6} and a = 9999 (or any other large odd number) shows the advantages of this algorithm. It is easy to see that odd numbers can never be plotted, and we would fill the entire set with all even numbers except 2. But if we divide by gcd, we get d = {2, 3} and aUp = 5000 and aDown = 4999. Number Frobenius for {2, 3} is 1 (the only number that cannot be built), so after no more than 3 (the first number where everything is covered in modulus) steps (instead of 10000), the modulus will be zero, and we will return a * gcd, which gives 9998 or 10000 depending on the rounding direction, which is the correct result.
Here is the code with test included. I made six runs on my crappy notebook, and it took 90, 92, 108, 94, 96 and 101 seconds ( the edit : escape at the beginning of the cycle, if the current denomination is greater than the current number && n - d[i] >= 0
reduces the time and gives an average of about 45 seconds ) to 7200 random rounds (3600 in each direction) with combinations of different numbers of denominations (2 to 100), dMax (range 100 to 10 ^ 6) and aMax (range 10 ^ 4 to 10 ^ 6) (see code below for exact values ). I think the time to generate and output random numbers can be neglected, so with this input and given ranges, the algorithm rounds about 160 numbers per second on average ( edit: see 30 times faster version below ) ..
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");
}
As @Koray edit 7 turned out to be about three times faster for a given input (only for very large gcds my above algorithm is faster). So, to get the final algorithm , I replaced some of the dynamic programming of my algorithm with @Koray (with some improvements). It worked, it's about ten times faster than edit 7 and thirty times faster than the algorithm above . Which will give an average of about 5000 roundings per second (very rough estimate).
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;
}
source to share
I tried it in a simple way. I hope I haven't misunderstood the problem and it's not too stupid :)
private static void test()
{
var amount = 61;
int[] denoms = new int[] { 20, 50 };
int up = RoundAmount(amount, denoms, true);//->70
int down = RoundAmount(amount, denoms, false);//->60
}
private static int RoundAmount(int amount, int[] denoms, bool roundUp)
{
HashSet<int> hs = new HashSet<int>(denoms);
bool added = true;
while (added)
{
added = false;
var arr = hs.ToArray();
foreach (int v1 in arr)
foreach (int v2 in arr)
if ((v1 < amount) && (v2 < amount) && (hs.Add(v1 + v2)))
added = true;
}
int retval = roundUp ? int.MaxValue : int.MinValue;
foreach (int v in hs)
{
if (roundUp)
{
if ((v < retval) && (v >= amount))
retval = v;
}
else
{
if ((v > retval) && (v <= amount))
retval = v;
}
}
return retval;
}
Please let me know if this feature is inadequate or has problems. Having a vote without knowing the reason, I feel bad. Thank.
Edit 7 - There was an error in editor 6 if the character "0" exists. I have studied @maraca's code in detail (it seems very cool to me) and I inspired it, I tried some optimizations in my code. Here's a performance comparison. (I was trying to convert the maraca code to C #, I hope I did it right.)
private static int REPEAT = 100;
private static int[] D_COUNT = { 2, 5, 10, 20, 50, 100 };
private static int[] D_MAX = { 100, 10000, 1000000 };
private static int[] A_MAX = { 10000, 1000000 };
private static void testR()
{
Random r = new Random();
long wMaraca = 0;
long wKoray = 0;
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.Next(D_MAX[k]);
int a = r.Next(A_MAX[l]);
Stopwatch maraca = Stopwatch.StartNew();
int m1 = RoundAmount_maraca(a, d, false);
int m2 = RoundAmount_maraca(a, d, true);
maraca.Stop();
wMaraca += maraca.ElapsedMilliseconds;
Stopwatch koray = Stopwatch.StartNew();
int k1 = RoundAmount_koray(a, d, false);
int k2 = RoundAmount_koray(a, d, true);
koray.Stop();
wKoray += koray.ElapsedMilliseconds;
if ((m1 != k1) || (m2 != k2))
{
throw new Exception("something is wrong!");
}
}
}
}
}
//some results with debug compile
//try1
//maraca: 50757 msec
//koray: 19188 msec
//try2
//maraca: 52623 msec
//koray: 19102 msec
//try3
//maraca: 57139 msec
//koray: 18952 msec
//try4
//maraca: 64911 msec
//koray: 21070 msec
}
private static int RoundAmount_koray(int amount, int[] denoms, bool roundUp)
{
List<int> lst = denoms.ToList();
lst.Sort();
if (amount < lst[0])
return roundUp ? lst[0] : 0;
HashSet<int> hs = new HashSet<int>();
for (int i = 0, count = lst.Count; i < count; i++)
{
int v = lst[i];
if (v != 0)
{
if (v > amount && !roundUp)
break;
if (hs.Add(v))
{
if (amount % v == 0)
return amount;
else
for (int j = i + 1; j < count; j++)
if (lst[j] != 0)
if (v % lst[j] == 0)
lst[j] = 0;
else if (amount % (v + lst[j]) == 0)
return amount;
}
}
}
denoms = hs.ToArray();
HashSet<int> hsOK = new HashSet<int>(denoms);
Stack<int> st = new Stack<int>(denoms);
BitArray ba = new BitArray(amount + denoms.Max() * 2 + 1);
int minOK = amount - denoms.Min();
while (st.Count > 0)
{
int v1 = st.Pop();
foreach (int v2 in denoms)
{
int val = v1 + v2;
if (!ba.Get(val))
{
if (amount % val == 0)
return amount;
ba.Set(val, true);
if (val < amount)
st.Push(val);
if (val >= minOK)
hsOK.Add(val);
}
}
}
if (!roundUp)
{
int retval = 0;
foreach (int v in hsOK)
if (v > retval && v <= amount)
retval = v;
return retval;
}
else
{
int retval = int.MaxValue;
foreach (int v in hsOK)
if (v < retval && v >= amount)
retval = v;
return retval;
}
}
private static int RoundAmount_maraca(int a, int[] d, bool up)
{
d = d.ToArray();
Array.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;
}
var set = new HashSet<int>();
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;
}
}
}
}
private static int euclid(int a, int b)
{
while (b != 0)
{
int h = a % b;
a = b;
b = h;
}
return a;
}
Edit - Maraca in C #
The latest Maraca update is clearly superior! I tried to prepare a better C # transformation of my code + added the ulong version. (int version is 1.6 times faster than ulong version)
#region maraca int
private static int RoundAmount_maraca(int a, int[] d0, bool up)
{
int[] d = new int[d0.Length];
Buffer.BlockCopy(d0, 0, d, 0, d.Length * sizeof(int));
Array.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;
}
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--;
}
var st = new Stack<int>();
BitArray ba = new BitArray(a+1);
for (int i = 0; i < count; i++)
{
ba.Set(d[i], true);
st.Push(d[i]);
}
while (st.Count > 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 (up && val > a && val < best)
best = val;
}
}
return best * gcd;
}
private static int euclid(int a, int b)
{
while (b != 0)
{
int h = a % b;
a = b;
b = h;
}
return a;
}
#endregion
#region maraca ulong
private static ulong RoundAmount_maraca_ulong(ulong a, ulong[] d0, bool up)
{
ulong[] d = new ulong[d0.Length];
Buffer.BlockCopy(d0, 0, d, 0, d.Length * sizeof(ulong));
Array.Sort(d);
if (a < d[0])
return up ? d[0] : 0ul;
int count = 0;
for (int i = 0; i < d.Length; i++)
{
if (d[i] == 0ul)
continue;
for (int j = i + 1; j < d.Length; j++)
if (d[j] % d[i] == 0ul)
d[j] = 0ul;
if (d[i] > a && !up)
break;
d[count++] = d[i];
if (d[i] > a)
break;
}
if (count == 1)
return (!up ? a : (a + d[0] - 1ul)) / d[0] * d[0];
ulong 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 - 1ul) / gcd;
else
a /= gcd;
for (int i = 0; i < count; i++)
{
d[i] /= gcd;
if (a % d[i] == 0ul)
return a * gcd;
}
ulong best = !up ? d[count - 1] : ((a + d[0] - 1ul) / d[0] * d[0]);
if (d[count - 1] > a)
{
if (d[count - 1] < best)
best = d[count - 1];
count--;
}
var st = new Stack<ulong>();
UlongBitArray ba = new UlongBitArray(a + 1ul);
for (int i = 0; i < count; i++)
{
ba.Set(d[i], true);
st.Push(d[i]);
}
while (st.Count > 0)
{
ulong v1 = st.Pop();
for (int i = 0; i < count; i++)
{
ulong val = v1 + d[i];
if (val <= a && !ba.Get(val))
{
if ((a - val) % d[0] == 0ul)
return a * gcd;
ba.Set(val, true);
st.Push(val);
if (!up && val > best)
best = val;
}
else if (up && val > a && val < best)
best = val;
}
}
return best * gcd;
}
private static ulong euclid(ulong a, ulong b)
{
while (b != 0)
{
ulong h = a % b;
a = b;
b = h;
}
return a;
}
class UlongBitArray
{
ulong[] bits;
public UlongBitArray(ulong length)
{
this.bits = new ulong[(length - 1ul) / 32ul + 1ul];
}
public bool Get(ulong index)
{
return (this.bits[index / 32ul] & (1ul << (int)(index % 32ul))) > 0ul;
}
public void Set(ulong index, bool val)
{
if (val)
this.bits[index / 32ul] |= 1ul << (int)(index % 32ul);
else
this.bits[index / 32ul] &= ~(1ul << (int)(index % 32ul));
}
}
#endregion
Edit 8
I've made some improvements and outperformed @maraca's latest update in random tests :) If you decide to use my own stack class , take measurements in release mode . (This custom stack class is of course much slower in debug mode, but% 5-15 is faster than .NET in relase mode. In my tests using the .NET Stack class, the performance comparison between the two has not changed, this is just an additional boost.)
private delegate int RoundAmountDelegate(int amount, int[] denoms, bool roundUp);
private static int REPEAT = 100;
private static int[] D_COUNT = { 2, 5, 10, 20, 50, 100 };
private static int[] D_MAX = { 100, 10000, 1000000 };
private static int[] A_MAX = { 10000, 1000000 };
private static void testR()
{
#if DEBUG
while (true)
#endif
{
Random r = new Random();
long wT1 = 0; RoundAmountDelegate func1 = RoundAmount_maraca;
long wT2 = 0; RoundAmountDelegate func2 = RoundAmount_koray;
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]];
ulong[] dl = new ulong[D_COUNT[j]];
for (int m = 0; m < d.Length; m++)
{
d[m] = r.Next(D_MAX[k]) + 1;
dl[m] = (ulong)d[m];
}
int a = r.Next(A_MAX[l]);
ulong al = (ulong)a;
Stopwatch w1 = Stopwatch.StartNew();
int m1 = func1(a, d, false);
int m2 = func1(a, d, true);
w1.Stop();
wT1 += w1.ElapsedMilliseconds;
Stopwatch w2 = Stopwatch.StartNew();
int k1 = func2(a, d, false);
int k2 = func2(a, d, true);
w2.Stop();
wT2 += w2.ElapsedMilliseconds;
if ((m1 != k1) || (m2 != k2))
{
#if !DEBUG
MessageBox.Show("error");
#else
throw new Exception("something is wrong!");
#endif
}
}
}
}
}
//some results with release compile
//maraca: 1085 msec
//koray(with .NET Stack<int>): 801 msec
//maraca: 1127 msec
//koray(with .NET Stack<int>): 741 msec
//maraca: 989 msec
//koray(with .NET Stack<int>): 736 msec
//maraca: 962 msec
//koray(with .NET Stack<int>): 632 msec
//-------------------------------------------
//maraca: 1045 msec
//koray(with custom stack): 674 msec
//maraca: 1060 msec
//koray(with custom stack): 606 msec
//maraca: 1175 msec
//koray(with custom stack): 711 msec
//maraca: 878 msec
//koray(with custom stack): 699 msec
#if !DEBUG
MessageBox.Show(wT1 + " " + wT2 + " %" + (double)wT2 / (double)wT1 * 100d);
#endif
}
}
#region Koray
private static int RoundAmount_koray(int amount, int[] denoms, bool roundUp)
{
int[] sorted = new int[denoms.Length];
Buffer.BlockCopy(denoms, 0, sorted, 0, sorted.Length * sizeof(int));
Array.Sort(sorted);
int minD = sorted[0];
if (amount < minD)
return roundUp ? minD : 0;
HashSet<int> hs = new HashSet<int>();
for (int i = 0, count = sorted.Length; i < count; i++)
{
int v = sorted[i];
if (v != 0)
{
if (!roundUp && v > amount)
break;
else if (hs.Add(v))
{
if (amount % v == 0)
return amount;
else
for (int j = i + 1; j < count; j++)
if (sorted[j] != 0)
if (v % sorted[j] == 0)
sorted[j] = 0;
else if (amount % (v + sorted[j]) == 0)
return amount;
}
}
}
denoms = new int[hs.Count];
int k = 0;
foreach (var v in hs)
denoms[k++] = v;
HashSet<int> hsOK = new HashSet<int>(denoms);
stack st = new stack(denoms);
//Stack<int> st = new Stack<int>(denoms);
BitArray ba = new BitArray(amount + denoms[denoms.Length - 1] * 2 + 1);
int minOK = roundUp ? amount : amount - minD;
int maxOK = roundUp ? amount + minD : amount;
while (st.Count > 0)
{
int v1 = st.Pop();
foreach (int v2 in denoms)
{
int val = v1 + v2;
if (val <= maxOK)
{
if (!ba.Get(val))
{
if (amount % val == 0)
return amount;
int diff = amount - val;
if (diff % v1 == 0 || diff % v2 == 0)
return amount;
ba.Set(val, true);
if (val < amount)
st.Push(val);
if (val >= minOK)
hsOK.Add(val);
}
}
else
break;
}
}
if (!roundUp)
{
int retval = 0;
foreach (int v in hsOK)
if (v > retval && v <= amount)
retval = v;
return retval;
}
else
{
int retval = int.MaxValue;
foreach (int v in hsOK)
if (v < retval && v >= amount)
retval = v;
return retval;
}
}
private sealed class stack
{
int[] _array;
public int Count;
public stack()
{
this._array = new int[0];
}
public stack(int[] arr)
{
this.Count = arr.Length;
this._array = new int[this.Count*2];
Buffer.BlockCopy(arr, 0, this._array, 0, this.Count * sizeof(int));
}
public void Push(int item)
{
if (this.Count == this._array.Length)
{
int[] destinationArray = new int[2 * this.Count];
Buffer.BlockCopy(this._array, 0, destinationArray, 0, this.Count * sizeof(int));
this._array = destinationArray;
}
this._array[this.Count++] = item;
}
public int Pop()
{
return this._array[--this.Count];
}
}
#endregion
#region Maraca
private static int RoundAmount_maraca(int a, int[] d0, bool up)
{
int[] d = new int[d0.Length];
Buffer.BlockCopy(d0, 0, d, 0, d.Length * sizeof(int));
Array.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;
}
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--;
}
var st = new Stack<int>();
BitArray ba = new BitArray(a + 1);
for (int i = 0; i < count; i++)
{
ba.Set(d[i], true);
st.Push(d[i]);
}
while (st.Count > 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 (up && val > a && val < best)
best = val;
}
}
return best * gcd;
}
private static int euclid(int a, int b)
{
while (b != 0)
{
int h = a % b;
a = b;
b = h;
}
return a;
}
#endregion
source to share
This is a common issue with Knapsack and you can use it to link your wiki page to its concept.
I think your problem can be divided into two parts.
Make a denomination backpack.
Use f[i]
to represent the last denomination used to create the amount i
, f[i]==-1
meaning it i
cannot receive.
fill f with -1
f[0] = 0
for i from 0 to target_amount + min(denoms) - 1
for j from 0 to denoms.size()
if f[i - denoms[j]] != -1
{
f[i] = denoms[j]
break
}
Find the closest amount based on roundUp
.
-
roundUp == true
Starting from target_amount
, in ascending order, find a f[i]
that is not -1
.
-
roundUp == false
Starting with target_amount
, descending, find f[i]
which is not -1
.
Optional: find which denominations will build the target amount
Give up yours f[target_amount]
.
source to share
Just populate the length array with amount + smallestdenomination + 1
possible coin combinations (standard dynamic programming problem).
Then traverse this array from the index amount
in the direction of rounding.
Delphi example
var
A : array of Integer;
Denoms: array of Integer;
coin, amount, idx, i, Maxx: Integer;
roundUp: Boolean;
s: string;
begin
amount := 29;
SetLength(Denoms, 2);
Denoms[0] := 7;
Denoms[1] := 13;
Maxx := amount + MinIntValue(Denoms);
SetLength(A, Maxx + 1);
A[0] := 1;
for coin in Denoms do begin
for i := 0 to Maxx - coin do
if A[i] <> 0 then
A[i + coin] := coin;
end;
roundUp := True;
idx := amount;
i := 2 * Ord(roundUp) - 1;// 1 for roundUp=true, -1 for false
while A[idx] = 0 do //scan for nonzero entry
idx := idx + i;
s := '';
while idx > 0 do begin //roll back to get components of this sum
s := s + Format('%d ', [A[idx]]);
idx := idx - A[idx];
end;
Memo1.Lines.Add(s);
outputs the 13 13 7
combination for roundUp := True;
and 7 7 7 7
otherwise.
(The code is not looking for an "optimal" solution)
Example for coins 3 and 5:
[0, 0, 0, 3, 0, 5, 3, 0, 5, 3, 5]
To find out which coins make cell 8, step down the cell value: by 5, then by 3.
source to share
The coin problem is a well researched topic and I would like to refer to some articles where you will probably find better solutions:
Also, using C # (a statically typed language) will limit you to having the most efficient algorithm in a dynamically typed language. If you are planning to go down this route, you can look at this site for the Frobenius Problem . You can right click and inspect the code (although I didn't really understand that I have no experience with javascript)
Anyway, here's how I might solve the problem in C #:
private static List<int> _denominations = new List<int>() { 1000, 5000 };
private static int _denominationMin = _denominations[0];
static void Main()
{
bool roundDown = false;
Console.WriteLine("Enter number: ");
int input = Convert.ToInt32(Console.ReadLine());
if(roundDown)
{
for(int i = input; i > _denominationMin; i--)
{
if(Check(0,0,i))
{
Console.WriteLine("Number: {0}", i);
break;
}
}
}
else
{
for (int i = input; i < int.MaxValue; i++)
{
if (Check(0, 0, i))
{
Console.WriteLine("Number: {0}", i);
break;
}
}
}
Console.Read();
}
static bool Check(int highest, int sum, int goal)
{
//Bingo!
if (sum == goal)
{
return true;
}
//Oops! exceeded here
if (sum > goal)
{
return false;
}
// Loop through _denominations.
foreach (int value in _denominations)
{
// Add higher or equal amounts.
if (value >= highest)
{
if(Check(value, sum + value, goal))
{
return true;
}
}
}
return false;
}
Worked well with {4,6} for input 19999, so I don't think this is all bad. Of course, he has room for improvement without Stackoverflow Exception
. You could have half the input or a quarter. Or subtract a number that has factors, a subset of which are names. In addition, it is important to sort the denominations and not contain the multiplicity of another notation Ex {4, 6, 8} → {4, 6}.
Anyway, if I have time, I will try to make it more efficient. Just wanted to provide an alternative solution.
source to share