What kind of mathematical problem is this??

Estelle001 · 2006-07-07 00:26:23

Hi there!

I have a problem.... (yes, a dream to ). I need to solve a quite difficult mathematical problem (to me anyhow). I've been browsing the web for quite some hours now and still am puzzeled how to solve this problem in a program (would like to create a php program for this) or to find the mathematical solution. I've read about the knapsack problem, but I'm not sure I'm on the right track as my problem has no "weight" (I think... :s)

So, this is my challenge:
I have an unlimited number of coins, let's hypothetically say with value 5, 7, 10, 15, 25 and 50 (let's suppose this would exist in USD).
I want to fill my purse with a number of coins and the total value should be for example 71 USD with that restriction that I want 12 coins in my purse or a number of coins as close to 12. If 71 can not be composed with 12 coins, I need to find the combination of coins as close to 71 (but not higher !) with a number of coins as close to 12 (slightly below or slightly above).

Hm, even formulating the problem is not easy. I hope you understand the problem. Is this a knapsack problem??? Or should I look in another direction? Can s.o. give me a clue how to solve this? Even better.. If anyone would know a php program (or java or so) for it, that would be GREAT!? or the formula...

Maybe this problem is easier to you than to me (hope so).
thans to all !
Estelle.

Ricky · 2006-07-07 01:28:18

let's hypothetically say with value 5, 7, 10, 15, 25 and 50 (let's suppose this would exist in USD).

Do you mean to say that the coins can have any value, and this was an example of such values, or that the coins must have these values?

MathsIsFun · 2006-07-07 01:30:14

Just clarifying to begin with. Can you choose the coin values (5,7,10, etc) or are they given? For example binary powers (1,2,4,8,16,32,..) would help. And the "71", is that going to change each time?

If it is a general solution you are after, it sounds like it may indeed be in the "travelling salesman" class of problems that are officially called "NP-complete". Put simply, the time to solve the problem takes a lot longer each time you add complexity. Small problems are easy, but medium sized problems could take to the end of the universe to solve!

There is a known problem where you are given a set of integers (example: {-4, -2, -1, 3, 7, 9}) and want to answer the question "can you take some of them and have them add to zero?". This problem is known to be "NP-Complete".

(Not that this would help, but I once wrote a program for a supplier of steel bars - his problem was that people ordered many different lengths but his stock had only a few sizes, so he had an average 10% waste on cutting (example: someone wants 4m lengths and he has 6m bars). I got that down to 3% for him, and my battle was with time - in theory it could be years or millenia to solve, but he was willing to wait only 5 minutes after entering in the days orders, so I put together several algorithms and let them fight it out for 5 minutes!)

Estelle001 · 2006-07-07 02:00:24

Do you mean to say that the coins can have any value, and this was an example of such values, or that the coins must have these values?

No, the coins are of defined value. Only 5, 7, 10, 15, 25 and 50 USD coins exist. Only those values can be used. But there is no limit to the number of coins of each value I may use.

Just clarifying to begin with. Can you choose the coin values (5,7,10, etc) or are they given? For example binary powers (1,2,4,8,16,32,..) would help. And the "71", is that going to change each time?

The values are given. Only those coins are available. But as stated above, I can use for example as many 5 USD coins as I should need in the optimal solution...
The "71" will change every time. Could be any other figure, but of course, will be limited somehow otherwise the algorithm would calculate eternally . For example, the maximum would be around 300 USD

Just an example: 285 USD would result in 11*25 and 1*10 (so, the total is 285, and I have exactly 12 coins)...

Ricky · 2006-07-07 02:43:23

If it's an algorithm you want, then that's easy. Try every single combination

5, 7, 10, 15, 25 and 50 are the values. If you can only use x coins, there are 6^x combinations. So trying every combination doesn't take too long until you get to problems dealing with 12 or more coins.

Then of course, there are optimizations. For example, if you were sure that you would have to include at least one 50 piece, then you could eliminate millions of combinations right from the get-go.

I'll write one up a bit later.

John E. Franklin · 2006-07-07 12:39:48

Hi! If it were me I would just always carry 13 coins in my purse, the same ones all the time.
I would pick four 5's, four 7's, and five 50's. Then I can get pretty close to any number, but the
drawback is that for lots of combinations you will use much less than 12 coins. Oh well.

Or if you must be picky, then take your number and subtract 7 up to four times until the number
ends in a zero or a five. Then divide the 5 multiple number by coins left after 7's used. Use one or
two coins that are bigger than the division answer you just got. Do another division by dividing by
the number less one or two coins you just picked. Do some examples and you'll see you can always
do it exactly for 300 down to maybe 68, just a guess (40 + 28).

Let's try 69, 69 - 7 - 7 ends in 5. ten coins left for 55. nine 5's and a ten.
Let's try 71, 71 - 7 - 7 - 7 ends in 0, nine coins left for 50. eight 5's and a ten.
Let's try 72, 72 - 7 ends in a 5, so 11 coins left for 65. (65/11 estimate) two 10's and nine 5's.
Let's try 73, 73 - 7 - 7 - 7 - 7 ends in 5, so 8 coins left for 45 (45/8 estimate) seven 5's and one 10.

Seems to be working.

Ricky · 2006-07-08 17:28:36

Here is code that tries every combination. You supply the target number, the coin values to be used, and the number of coins to be used:

#include <iostream>
#include <vector>

using namespace std;

void dispArrayAndSum(vector<int> array) {
	int x;
	cout << "{";
	int sum = 0;
	for (x = 0; x < array.size()-1; x++) {
		cout << array[x] << ", ";
		sum += array[x];
	}
	cout << array[array.size()-1] << "}" << endl;
	sum += array[array.size()-1];
	cout << "Sum: " << sum << endl;
}

vector<int> getNextCombo(vector<int> coins, vector<int> usedCoins, int numCoins) {
	int x, y;
	if (usedCoins.size() == 0) {
		for (x = 0; x < numCoins; x++) {
			usedCoins.push_back(coins[0]);
		}
	}
	else {
		for (x = numCoins-1; x != -1; x--) {
			if (usedCoins[x] == coins[coins.size()-1]) {
				usedCoins[x] = coins[0];
			}
			else {
				for (y = 0; y < coins.size(); y++) {
					if (usedCoins[x] == coins[y]) {
						break;
					}
				}
				usedCoins[x] = coins[y+1];
				break;
			}
		}
	}
	/*cout << "HERE: ";
	dispArrayAndSum(usedCoins);
	cout << endl;*/
	return usedCoins;
}

bool keepGoing(vector<int> coins, vector<int> usedCoins) {
	int x;
	for (x = 0; x < usedCoins.size(); x++) {
		if (usedCoins[x] != coins[coins.size()-1]) break;
	}
	return x != usedCoins.size();
}

vector<int> makeAmount(int target, vector<int> coins, int numCoins) {
	int x, leastDiff = target;
	vector<int> usedCoins;
	usedCoins = getNextCombo(coins, usedCoins, numCoins);
	vector<int> leastDiffValues = usedCoins;
	while (keepGoing(coins, usedCoins)) {
		int sum = 0;
		for(x = 0; x < usedCoins.size(); x++) {
			sum += usedCoins[x];
		}
		if (abs(target - sum) < leastDiff) {
			leastDiff = abs(target - sum);
			leastDiffValues = usedCoins;
		}
		usedCoins = getNextCombo(coins, usedCoins, numCoins);
	}

	return leastDiffValues;
}

int main() {
	vector<int> coins; coins.push_back(5); coins.push_back(7); coins.push_back(10); 
	coins.push_back(15); coins.push_back(25); coins.push_back(50);

	int target, x;
	int numCoins = 6;
	for (target = 30; target < 50; target++) {
		vector<int> result = makeAmount(target, coins, numCoins);
		cout << "Target: " << target << endl;
		cout << "Coins: ";
		dispArrayAndSum(result);
		cout << endl;
	}
	return 0;
}

It takes a fraction of a second to run for each value with 6 coins. It takes minutes for 10 coins. Anyone suggest ways of not testing all values?

One way I think would work is to divide the target by the number of coins. This will give you an average value for each coin. Then find the closest value coin to that, and fill an array all with that coin. Then, start replacing coins with values that will make the difference less.

But it's late, I'll work on that one tomorrow.

MathsIsFun · 2006-07-08 22:14:34

Jeepers, good work Ricky.

If it is indeed NP-complete (and I suspect it is), it is a widely-researched subject with lots of algorithms, most aimed at getting as close as possible in a short time (with the knowledge that the exact answer needs an exhaustive search which takes impossibly long).

So, apart from quickly rejecting bad answers (like "we are already over the total") I can't see any other way to hasten a best answer. But there are lots of ways to hasten a close answer. Genetic Algorithms are some of the coolest ones.

Bit lazy of me just to talk generalities, though

Found a wikipedia article that may help: http://en.wikipedia.org/wiki/Subset_sum_problem

Ricky · 2006-07-09 03:57:10

Ok, this code will solve for coins of up to size 100 in mere fractions of a second:

#include <iostream>
#include <vector>

using namespace std;

int Sum(vector<int> array) {
	int result = 0;
	int x;
	for (x = 0; x < array.size(); x++) {
		result += array[x];
	}
	return result;
}

void dispArrayAndSum(vector<int> array) {
	int x;
	cout << "{";
	for (x = 0; x < array.size()-1; x++) {
		cout << array[x] << ", ";
	}
	cout << array[array.size()-1] << "}" << endl;
	cout << "Sum: " << Sum(array) << endl;
}

vector<int> getNextCombo(int target, vector<int> coins, vector<int> usedCoins) {
	int x, y;
	int diff = abs(Sum(usedCoins) - target);
	int sum;
	for (x = 0; x < usedCoins.size(); x++) {
		for (y = 0; y < coins.size(); y++) {
			int temp = usedCoins[x];
			usedCoins[x] = coins[y];
			if (abs(Sum(usedCoins) - target) < diff) {
				return usedCoins;
			}
			usedCoins[x] = temp;
		}
	}
	return usedCoins;
}

bool keepGoing(int target, vector<int> coins, vector<int> usedCoins) {
	int sum = 0;
	int x;
	for (x = 0; x < usedCoins.size(); x++) {
		sum += usedCoins[x];
	}
	if (sum == target) return false;

	for (x = 0; x < usedCoins.size(); x++) {
		if (usedCoins[x] != coins[coins.size()-1]) break;
	}
	return x != usedCoins.size();
}

vector<int> initArray(int target, vector<int> coins, int numCoins) {
	vector<int> result;
	int avg = target / numCoins;
	int diff = avg;
	int diffCoin = coins[0];
	int x;
	for (x = 0; x < coins.size(); x++) {
		if (abs(coins[x] - avg) < diff) {
			diff = abs(coins[x] - avg);
			diffCoin = coins[x];
		}
	}

	for (x = 0; x < numCoins; x++) {
		result.push_back(diffCoin);
	}

	return result;
}

bool areEqual(vector<int> oldCoins, vector<int> usedCoins) {
	if (oldCoins.size() != usedCoins.size()) return false;
	int x;
	for (x = 0; x < oldCoins.size(); x++) {
		if (oldCoins[x] != usedCoins[x]) break;
	}
	return x == usedCoins.size();
}

vector<int> makeAmount(int target, vector<int> coins, int numCoins) {
	int x, leastDiff = target;
	vector<int> usedCoins = initArray(target, coins, numCoins);
	vector<int> leastDiffValues = usedCoins;
	vector<int> oldCoins;
	while (keepGoing(target, coins, usedCoins) && !areEqual(oldCoins, usedCoins)) {
		int sum = 0;
		for(x = 0; x < usedCoins.size(); x++) {
			sum += usedCoins[x];
		}
		if (abs(target - sum) < leastDiff) {
			leastDiff = abs(target - sum);
			leastDiffValues = usedCoins;
		}
		oldCoins = usedCoins;
		usedCoins = getNextCombo(target, coins, usedCoins);
	}

	return leastDiffValues;
}

int main() {
	vector<int> coins; coins.push_back(5); coins.push_back(7); coins.push_back(10); 
	coins.push_back(15); coins.push_back(25); coins.push_back(50);

	int target, x;
	int numCoins = 100;
	for (target = 1000; target < 1010; target++) {
		vector<int> result = makeAmount(target, coins, numCoins);
		cout << "Target: " << target << endl;
		cout << "Coins: ";
		dispArrayAndSum(result);
		cout << endl;
	}
	return 0;
}

However, it still uses some fairly slow algorthms in it. For example, if I change one coin, it calculates the sum by adding up all the numbers again, even though the previous sum is known. All I would really have to do is take the difference of what I'm replacing and what I'm replacing it with, and add that to the previous sum.

Ricky · 2006-07-09 03:58:28

If the number of coins is 1000, then it takes about 5 seconds.

Edit: Nevermind, that was in debug mode. In release mode (where compiler optimizations are made), it still takes fractions of a second.

Estelle · 2006-07-10 00:28:55

Hi Ricky,

I would like to test the code. What language is it? C, C++, Java?
Should have the <iostream> and <vector> include also...
How should I do to be able to run?

thanks !

Ricky · 2006-07-10 01:49:30

It is C++. I can make it so that there will just be an executable in which you type all the parameters in, so that you don't need to know how to program to use it. But there is a problem with that. I would be sending you an executable, and thus, you have to trust me that I don't put any dangerous code in there.

Of course, I can garuantee that I won't, but you are still going to have to be taking my word for it. There is no way to verify that I would put anything bad in there.

Estelle · 2006-07-10 02:49:35

That would be great ! How can you send it? by e-mail ? Downloadable on some URL? or something like that?

MathsIsFun · 2006-07-10 11:48:08

OK, so the problem must not be NP-complete, there must be some essential difference to the "Subset Sum Problem", which is known to be NP-complete, or else you should be seeing dramatic increases in time for larger problem sizes.

Rough explanation: if you measure how long a program takes to run when given more and more difficult problems, such as sorting a list of 10 items, 20 items, 30 items etc, you can then plot the times and come up with a function. For example the time might increase by x², so a problem that is twice as hard takes 4 times as long. That program would be in "P", as it is solvable in "Polynomial" time. But if the time went up logarithmically or factorially, or something that exceeds what a polynomial can do, it would not be in "P".

Now, the "N" in "NP" refers to the fact that you are not bound by the normal way a computer works, which is step-by-step. The "N" actually stands for "Non-deterministic". This means that you are dealing with an amazing kind of computer that can run things simultaneoulsy or could somehow guess the right way to do things, or something like that. So this "N" computer can solve lots more problems in "P" time - for example it can just clone copies of itself when needed.

So, programs that take dramatically longer as the problem gets harder (ie not in "P") could be solved quickly on this "N" computer and so are in "NP". Thus "NP" means "we can solve it in polynomial time if we can break the normal rules of step-by-step computing".

Since this amazing "N" computer can also do anything a normal computer can, we know that "P" problems are also in "NP".

So, the easy programs are in "P" (and also in "NP"), but the really hard ones are *only* in "NP", and they are called "NP-complete".

It is like saying there are things that People can do ("P"), there are things that SuperPeople can do ("SP"), and there are things *only* SuperPeople can do ("SP-complete").

My apologies if I have bent the truth a little in this rough description.

Oh, one more thing, it is believed that if anyone could *ever* solve an "NP-Complete" problem in "P" time, then *all* "NP-complete" problems could also be solved that way, and the whole class of "NP-Complete" would cease to exist.

Ricky · 2006-07-10 14:09:54

The way in which my 2nd algorithm works, I don't believe it is NP.

My algorithm uses the average value each coin must have, and find the coin value closest to it to start off.

Then, it goes through each coin to find a better value of that coin which makes the sum closer to the target sum.

Since I start off with an approximate average, most of my coins are already the right values, no matter how many coins I have.

Estelle01 · 2006-07-12 09:26:56

Hi Ricky !
Could you send me the executable(s) of the program(s)? :-)
Thanks so much !
Estelle

Ricky · 2006-07-12 10:11:52

Sorry about the delay. Now I must warn you again that you should really not trust me, as this exe could do just about anything to your computer. But with that said:

http://www.filefactory.com/?737377

Copy and paste the above link, it will take you to an online file hoster. From there, you download the file (called coin.zip), extract it, and run coins.exe.

I have no idea what OS it will run on, but it should run on any XP.

Once again, use at your own risk.

MathsIsFun · 2006-07-12 11:52:48

If you ever need to do an investigation or project, you could try applying you algorithm to the Subset Sum Problem (http://en.wikipedia.org/wiki/Subset_sum_problem)

Math Is Fun Forum

#1 2006-07-07 00:26:23

What kind of mathematical problem is this??

#2 2006-07-07 01:28:18

Re: What kind of mathematical problem is this??

#3 2006-07-07 01:30:14

Re: What kind of mathematical problem is this??

#4 2006-07-07 02:00:24

Re: What kind of mathematical problem is this??

#5 2006-07-07 02:43:23

Re: What kind of mathematical problem is this??

#6 2006-07-07 12:39:48

Re: What kind of mathematical problem is this??

#7 2006-07-08 17:28:36

Re: What kind of mathematical problem is this??

#8 2006-07-08 22:14:34

Re: What kind of mathematical problem is this??

#9 2006-07-09 03:57:10

Re: What kind of mathematical problem is this??

#10 2006-07-09 03:58:28

Re: What kind of mathematical problem is this??

#11 2006-07-10 00:28:55

Re: What kind of mathematical problem is this??

#12 2006-07-10 01:49:30

Re: What kind of mathematical problem is this??

#13 2006-07-10 02:49:35

Re: What kind of mathematical problem is this??

#14 2006-07-10 11:48:08

Re: What kind of mathematical problem is this??

#15 2006-07-10 14:09:54

Re: What kind of mathematical problem is this??

#16 2006-07-12 09:26:56

Re: What kind of mathematical problem is this??

#17 2006-07-12 10:11:52

Re: What kind of mathematical problem is this??

#18 2006-07-12 11:52:48

Re: What kind of mathematical problem is this??

Board footer