Public Group

# Finding a target from a list of numbers

This topic is 2939 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a list of non unique numbers and I need to find which numbers add up closest to a target but never exceeding it. I would like to find the highest numbers possible from the list with the lowest remainder.

How do I even start doing this?.

I have been breaking my head... tried brute forcing it.... works well of course but takes ages if the list is > 50 numbers and sometimes the list is as large at 300 numbers.

##### Share on other sites

I have a list of non unique numbers and I need to find which numbers add up closest to a target but never exceeding it. I would like to find the highest numbers possible from the list with the lowest remainder.

How do I even start doing this?.

I have been breaking my head... tried brute forcing it.... works well of course but takes ages if the list is > 50 numbers and sometimes the list is as large at 300 numbers.

Try a greedy algorithm, or sort the list from high to low then add untill you reach the treshhold or addding the next number will exceed the threshold.You should be carefull that the low numbers don't exceed the high ones when added together because you might at that point be better of adding the low ones.

##### Share on other sites
Havn't thought this through, but would it possibly make it easier for you if you sort your numbers first?
Then start from the highest numbers and add more and more numbers until you are just below the goal, but the next number would exceed.
Then try swapping in numbers from the rest of the list if the swap would lower the remainder..
(removing one big, and adding as many small as there will fit)

That would fill up the set with the biggest possible numbers first, and then try to "pad" the rest with as big numbers as possible.

Well, as I said, havn't thought it through much, not sure if this is what you look for, or if it even works, but maybe something along those lines?

In any case it feels like a good idea to sort the array first...

Edit: NightCreature beat me to it with a shorter description of more or less the same thing

##### Share on other sites
Homework help is frowned upon in these forums. Part of what you're learning is how to apply knowledge to problems. Having us do that will only harm you in the long run.

##### Share on other sites
First of all this is not homework... Wish it was then i knew where to go look for even the beginning of an answer.

Need to go look up that greedy algorithm but I think I got an idea....

Indeed might try and addup the highest numbers till I reach the target.

Then search for each of those numbers a replacement + the rest of what I am searching for...

Thanks guys... will let you know when I find it.

##### Share on other sites

First of all this is not homework... Wish it was then i knew where to go look for even the beginning of an answer.

Need to go look up that greedy algorithm but I think I got an idea....

Indeed might try and addup the highest numbers till I reach the target.

Then search for each of those numbers a replacement + the rest of what I am searching for...

Thanks guys... will let you know when I find it.

I learned this in Uni in a algorithm desgin class the book we used is "Introduction to Algorithms". It was one of the most usefull classes I have followed at uni. The book lists more then just greedy algorithms and algorithm construction, also talks about sorting, graphs and matrices, it is one of those books you are actually glad you spent the money on in the rest of your career.

The problem you described is known as the knapsack problem and greedy algorithms general solve these fairly efficient.

##### Share on other sites
This is indeed a version of the knapsack problem, and there is a lot of information about it on Wikipedia.

If the numbers are integers and the target is reasonably small, you can use dynamic programming to solve this quite efficiently. If not, I would go for an approximate solution, using something like simulated annealing.

##### Share on other sites
I think I got it working at least for my needs... this procedure can take a long time when feeding it a lot of numbers where it can't reach it's goal

ex
three times 1001, 2001, 3001, 4001, 5001, 6001, 7001, 8001, 9001, 1002, 2002, 3002, 4002, 5002, 6002, 7002, 8002, 9002

and then sending it after 100000 but for my cases it will do just fine.

 /// <summary> /// Finds from a list of numbers /// the numbers that add up closest to a target /// Returns a list of numbers that added up are the closest to the target /// Also returns the rest /// </summary> public static class Knapsack { //for further optimizing... not sure if it will work //static DuplicateDictionary<int, List<int>> Combinations; /// <summary> /// used for sorting numbers High to low /// </summary> /// <param name="x">First number</param> /// <param name="y">Second number</param> /// <returns></returns> private static int CompareHighestFirst(int x, int y) { return y.CompareTo(x); } public static int iterations =0; /// <summary> /// Finds from a list of numbers /// the numbers that add up closest to a target /// Returns a list of numbers that added up are the closest to the target /// Also returns the rest /// </summary> /// <param name="target">Number to be reached</param> /// <param name="numbers">List of numbers to chose from</param> /// <param name="rest">out rest of the target - sum </param> /// <returns>List of numbers</returns> public static List<int> FindBestMatch(int target, List<int> numbers, out int rest) { int sum = 0; bool HasOdd = false; numbers.Sort(CompareHighestFirst); List<int> numberList = (from n in numbers where n <= target select n).ToList(); List<int> bestList; //Check if have Odd Numbers //Make total sum pf numbers foreach (int i in numbers) { if ((!HasOdd) && (i % 2 == 1)) HasOdd = true; sum += i; } //if the total is lower than the target if (sum < target) { bestList = new List<int>(); //Make a list of all numbers foreach (int i in numbers) { bestList.Add(i); } rest = target - sum; return bestList; } else if ((!HasOdd) && (target % 2 == 1)) { //If there are only even nubers and target is odd //make target even target--; bestList = FindBestMatch1(target, numberList, out rest); //Add one to rest rest++; } else { //find the best numberlist bestList = FindBestMatch1(target, numberList, out rest); } return bestList; } private static List<int> FindBestMatch1(int target, List<int> numbers, out int rest) { iterations++; //lists and rest variables to store temp best results List<int> bestList = new List<int>(); int bestRest = target; //Only numbers lower than terget are required. sorted from high to low List<int> NumbersList = (from n in numbers where n <= target select n).ToList(); NumbersList.Sort(CompareHighestFirst); //make a copy of the list to use as new parameter List<int> TempList = NumbersList.ToList(); //only one number if (numbers.Count == 1) { //Just making sure can be removed if (numbers[0] < target) { bestList.Add(numbers[0]); bestRest = target - numbers[0]; } } else if (numbers.Count > 0) { //used to do the checks only ones int last = target + 1; foreach (int i in NumbersList) { if (last > i) { last = i; List<int> newList; int newRest; if (i == target) { //if target is found return it newList = new List<int>(); newList.Add(i); newRest = 0; } else { //it not found yet TempList.Remove(i); //remove ourself from the list //recusivly find the best solution for the rest of our target newList = FindBestMatch1(target - i, TempList, out newRest); newList.Add(i); //add ourself to the new list //For further optimisations No idea if it(s going to work //if (Combinations == null) //{ // Combinations = new DuplicateDictionary<int, List<int>>(); // Combinations.Add(target - newRest, newList); //} } if (newRest < bestRest) { bestList = newList; bestRest = newRest; if (bestRest == 0) { break; } } } } } rest = bestRest; //OutputList(target, bestList, rest); return bestList; } } 

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 9
• 11
• 15
• 21
• 26
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!