tricky algorithm problem involving dividing change (cents)(¢)

[Lugnut]

So I am way too lazy to type it again, so have some reading.

Never tell your password to anyone.
Tuesday, November 27, 2012
10:56 PM - Lugnut: I have X dollars and Y cents in change
10:58 PM - Lugnut: I wish to make a script that will take the coins I have, and break them down into all the possible sets of combinations that makes Z$ and uses the most coins
10:58 PM - Lugnut: Sooo, loop through all the coins to divide them up or what
10:59 PM - Lugnut: How would I do that algorithmically
11:00 PM - Jetz: Uses the most coins...? Convert it all to pennies?
11:00 PM - Jetz: I'm not sure I understand the problem
11:04 PM - Lugnut: Say I have 1.25
11:05 PM - Lugnut: And that's 25¢, 4 nickels, 15 pennies, 4 dimes
11:06 PM - Lugnut: Um
11:06 PM - Lugnut: That's only 1$
11:06 PM - Lugnut: Ok yeah its 1$
11:06 PM - Lugnut: Broken down as stated
11:07 PM - Lugnut: I want to calculate how many possible combonations breaks it into 25¢ groups
11:07 PM - Lugnut: 15 pennies + 1 dime
11:07 PM - Lugnut: 5 pennies, 2 dimes
11:07 PM - Lugnut: Etc etc
11:08 PM - Lugnut: With the goal being to break it into the most optimal group for utilizing most of the coins
11:08 PM - Lugnut: ... without turning it into 100 pennies
11:09 PM - Jetz: Wait, break it into groups all using the same set of coins, like you can't use 15 pennies in 1 and 5 in another?
11:09 PM - Lugnut: Create a set of groups, where each group == 25¢
11:09 PM - Lugnut: Where the total is as close to 1$ as possible
11:11 PM - Jetz: And reuse is not aloud between groups? Sheesh that's a difficult problem. Would be annoying to even find a way to brute force that one.
11:11 PM - Lugnut: Correct
11:12 PM - Lugnut: It is allowed between sets

I realized after this line that it would be easier on every party involved's (did I just say involved's?) brain if I asked the whole of coding help instead.

A good way to think of this is that you have a stuffload of pocket change, and you want to figure out all the ways you want to create bus far.
This is a good comparison cause that's actually what I'm trying to do, lol.
If you have questions or suggestions, please post. You don't need actual code, we're talking algorithms here, not neccesarily code.

[Ad Bot]

[Trinick.]

Code: [Select]

function dollarsToCoins(%input)
{
%input *= 100;
%quarters = mFloor(%input / 25); // how many quarters
%input -= %quarters*25;
%dimes = mFloor(%input / 10); // how many dimes
%input -= %dimes*10;
%nickels = mFloor(%input / 5); // how many nickels
%input -= %nickels*5;
echo("$" @ %input SPC "in coins is:" SPC %quarters SPC "quarters," SPC %dimes SPC "dimes," SPC %nickels SPC "nickels," SPC %input SPC "pennies.");
}

That?

[Lugnut]

No.. I have X quarters, X dimes, X nickels, and X pennies

I have a target amount. I want to break the coins into groups that equal that amount, as many groups as possible.

[lilboarder32]

Can you handle this similar to how coin sorting machines work?
Start with large coins (quarters), fit as many as you can into desired amount, then once you can't fit anymore, move down to dimes, and so on... Then just reiterate the process?

[Lugnut]

Yes but that gives me only one possible solution, right?

[Trinick.]

Code: [Select]

function findValue(%total, %quota1, %quota2, %quota3, %quota4)
{
%dholder = new scriptObject();
%squota1 = %quota1;
%squota3 = %quota3;
%squota2 = %quota2;
%squota4 = %quota4;


for(%quota1=%squota1;%quota1 >= 0;%quota1--)
{
for(%i=1;%i<5;%i++) %quota[%i] = %squota[%i];
%input = %total;
%input *= 100;

%quarters = mFloor(%input / 25);
if(%quarters > %quota1) %quarters = %quota1;
%input1 = %input-%quarters*25;

for(%quota2=%squota2;%quota2 >= 0;%quota2--)
{
%dimes = mFloor(%input1 / 10);
if(%dimes > %quota2) %dimes = %quota2;
%input2 = %input1 - %dimes*10;

for(%quota3=%squota3;%quota3 >= 0;%quota3--)
{
%nickels = mFloor(%input2 / 5);
if(%nickels > %quota3) %nickels = %quota3;
%input3 = %input2 - %nickels*5;

for(%quota4=%squota4;%squota4>=0;%squota4--)
{
if(%input3 > %quota4)
break;
%dholder.list[%dholder.listc++-1] = %quarters SPC %dimes SPC %nickels SPC %input3;
}
}
}
}
return %dholder;
}
I haven't tested it but I think based on logic that should work.

Note: I've modified this post like 15 times finding small errors so don't expect it to work, just derive logic from it or think of it as something that needs to be fixed.

[lilboarder32]

Yes but that gives me only one possible solution, right?

Well it would give you as many groups as possible I believe, and I don't see another way to actually solve it, cuz you can hardly randomize the choosing.

[-Jetz-]

I don't see how breaking it into groups of equal amounts of money would result in more than one solution.
You can try a basic greedy algorithm:

Code: [Select]

function split(%c25, %c10, %c5, %c1, %size)
{
echo("---");
%curr = 0;
%u25 = 0;
%u10 = 0;
%u5 = 0;
%u1 = 0;
while(%c25 > 0 && %curr + 25 <= %size)
{
%c25--;
%u25++;
%curr += 25;
}
while(%c10 > 0 && %curr + 10 <= %size)
{
%c10--;
%u10++;
%curr += 10;
}
while(%c5 > 0 && %curr + 5 <= %size)
{
%c5--;
%u5++;
%curr += 5;
}
while(%c1 > 0 && %curr + 1 <= %size)
{
%c1--;
%u1++;
%curr += 1;
}
if(%size == %curr)
{
echo(%u25 SPC "quarters.");
echo(%u10 SPC "dimes.");
echo(%u5 SPC "nickels.");
echo(%u1 SPC "pennies.");
split(%c25, %c10, %c5, %c1, %size);
}
else
{
echo("Remainder:");
echo(%u25 + %c25 SPC "quarters.");
echo(%u10 + %c10 SPC "dimes.");
echo(%u5 + %c5 SPC "nickels.");
echo(%u1 + %c1 SPC "pennies.");
echo("---");
}
}
Totally untested and written entirely in the quick reply box.

[lilboarder32]

I don't see how breaking it into groups of equal amounts of money would result in more than one solution.
You can try a basic greedy algorithm:

Code: [Select]

-snip-
if(%size == %curr)
{
echo(%u25 SPC "quarters.");
echo(%u10 SPC "dimes.");
echo(%u5 SPC "nickels.");
echo(%u1 SPC "pennies.");
split(%c25, %c10, %c5, %c1, %size);
}
-snip-
Totally untested and written entirely in the quick reply box.

Your code works, you just have to change %total to %curr.

[-Jetz-]

Your code works, you just have to change %total to %curr.

Oh, whoops. Again, typed in the quick reply box and untested.

[Lugnut]

Okay what if I take a target change and find all the possible combinations using all the available resources, then brute-force-style calculate the possible ways said combos will fit (still making sure to not use too many coins!) Then order in the amount of total coins/money used

[-Jetz-]

Okay what if I take a target change and find all the possible combinations using all the available resources, then brute-force-style calculate the possible ways said combos will fit (still making sure to not use too many coins!) Then order in the amount of total coins/money used

Give us a few examples of what you want this function to calculate. Like actual input/output. Every time I think I get what you're talking about, you say something that confuses me again.

[Trinick.]

I don't see why you ignored my second post. You wanted code to list every possible combination of coins (limited by the values provided) that totals  a certain value. I gave you code that does that.

[Lugnut]

I don't see why you ignored my second post. You wanted code to list every possible combination of coins (limited by the values provided) that totals  a certain value. I gave you code that does that.

oops
I'll test this

Give us a few examples of what you want this function to calculate. Like actual input/output. Every time I think I get what you're talking about, you say something that confuses me again.

and post this if trinick's doesn't do what I want- I can use it as an example maybe

[¥ola]

We had a program exactly like this due in Introductory Computer Programming, using Visual Basic we used modular division, which used the "\" symbol, not sure if the same goes for Torquescript