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.
Can anyone please help me out?
Finding a target from a list of numbers
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.
Can anyone please help me out?
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.
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
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
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.
Author
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.
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.
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.
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.
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.
Author
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.
Thanks for all your pointers
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;
}
}
Thanks for all your pointers
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
