Subset sum problem
Solution 1:
How you should do this depends on a number important things: how many numbers will you have and how big will they be? Also, as far as I understand, your data can change (add / remove numbers etc.), right?. How often do you need to make these queries?
I'll present two solutions. I suggest you use the second, as I suspect it's better for what you need and it's a lot easier to understand.
Solution 1 - dynamic programming
Let S[i] = true if we can make sum i and false otherwise.
S[0] = true // we can always make sum 0: just don't choose any number
S[i] = false for all i != 0
for each number i in your input
for s = MaxSum downto i
if ( S[s - i] == true )
S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.
To get the actual numbers that make up your sum you should keep another vector P[i] = the last number that was used to make sum i. You would update this accordingly in the if condition above.
The time complexity of this is O(numberOfNumbers * maxSumOfAllNumbers), which is pretty bad, especially since you have to rerun this algorithm whenever your data changes. It's also slow for even one run as long as your numbers can be very big and you can have a lot of them. In fact, "a lot" is misleading. If you have 100 numbers and each number can be as big as 10 000, you will do roughly 100 * 10 000 = 1 000 000 operations each time your data changes.
It's a good solution to know, but not really useful in practice, or at least not in your case I think.
He's some C# for the approach I suggest:
class Program
{
static void Main(string[] args)
{
List<int> testList = new List<int>();
for (int i = 0; i < 1000; ++i)
{
testList.Add(1);
}
Console.WriteLine(SubsetSum.Find(testList, 1000));
foreach (int index in SubsetSum.GetLastResult(1000))
{
Console.WriteLine(index);
}
}
}
static class SubsetSum
{
private static Dictionary<int, bool> memo;
private static Dictionary<int, KeyValuePair<int, int>> prev;
static SubsetSum()
{
memo = new Dictionary<int, bool>();
prev = new Dictionary<int, KeyValuePair<int, int>>();
}
public static bool Find(List<int> inputArray, int sum)
{
memo.Clear();
prev.Clear();
memo[0] = true;
prev[0] = new KeyValuePair<int,int>(-1, 0);
for (int i = 0; i < inputArray.Count; ++i)
{
int num = inputArray[i];
for (int s = sum; s >= num; --s)
{
if (memo.ContainsKey(s - num) && memo[s - num] == true)
{
memo[s] = true;
if (!prev.ContainsKey(s))
{
prev[s] = new KeyValuePair<int,int>(i, num);
}
}
}
}
return memo.ContainsKey(sum) && memo[sum];
}
public static IEnumerable<int> GetLastResult(int sum)
{
while (prev[sum].Key != -1)
{
yield return prev[sum].Key;
sum -= prev[sum].Value;
}
}
}
You should do some error checking perhaps, and maybe store the last sum in the class so as not to allow the possibility of calling GetLastResult with a different sum than the sum Find was last called with. Anyway, this is the idea.
Solution 2 - randomized algorithm
Now, this is easier. Keep two lists: usedNums and unusedNums. Also keep a variable usedSum that, at any point in time, contains the sum of all the numbers in the usedNums list.
Whenever you need to insert a number into your set, also add it to one of the two lists (doesn't matter which, but do it randomly so there's a relatively even distribution). Update usedSum accordingly.
Whenever you need to remove a number from your set, find out which of the two lists it's in. You can do this with a linear seach as long as you don't have a lot (this time a lot means over 10 000, maybe even 100 000 on a fast computer and assuming you don't do this operation often and in fast succession. Anyway, the linear search can be optimized if you need it to be.). Once you have found the number, remove it from the list. Update usedSum accordingly.
Whenever you need to find if there are numbers in your set that sum to a number S, use this algorithm:
while S != usedSum
if S > usedSum // our current usedSum is too small
move a random number from unusedNums to usedNums and update usedSum
else // our current usedSum is too big
move a random number from usedNums to unusedNums and update usedSum
At the end of the algorithm, the list usedNums will give you the numbers whose sum is S.
This algorithm should be good for what you need, I think. It handles changes to the dataset very well and works well for a high number count. It also doesn't depend on how big the numbers are, which is very useful if you have big numbers.
Please post if you have any questions.
Solution 2:
Here is my algorithm. It runs in O(2^(n/2)) and solves SubsetSum(1000, list-of-1000-ones) in 20 milliseconds. See the comments at the end of IVlad's post.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace SubsetSum
{
class Program
{
static void Main(string[] args)
{
var ns = new List<int>();
for (int i = 0; i < 1000; i++) ns.Add(1);
var s1 = Stopwatch.StartNew();
bool result = SubsetSum(ns, 1000);
s1.Stop();
Console.WriteLine(result);
Console.WriteLine(s1.Elapsed);
Console.Read();
}
static bool SubsetSum(ist<int> nums, int targetL)
{
var left = new List<int> { 0 };
var right = new List<int> { 0 };
foreach (var n in nums)
{
if (left.Count < right.Count) left = Insert(n, left);
else right = Insert(n, right);
}
int lefti = 0, righti = right.Count - 1;
while (lefti < left.Count && righti >= 0)
{
int s = left[lefti] + right[righti];
if (s < target) lefti++;
else if (s > target) righti--;
else return true;
}
return false;
}
static List<int> Insert(int num, List<int> nums)
{
var result = new List<int>();
int lefti = 0, left = nums[0]+num;
for (var righti = 0; righti < nums.Count; righti++)
{
int right = nums[righti];
while (left < right)
{
result.Add(left);
left = nums[++lefti] + num;
}
if (right != left) result.Add(right);
}
while (lefti < nums.Count) result.Add(nums[lefti++] + num);
return result;
}
}
}
And here is an improved version that prunes the sets:
static bool SubsetSum(List<int> nums, int target)
{
var remainingSum = nums.Sum();
var left = new List<int> { 0 };
var right = new List<int> { 0 };
foreach (var n in nums)
{
if (left.Count == 0 || right.Count == 0) return false;
remainingSum -= n;
if (left.Count < right.Count) left = Insert(n, left, target - remainingSum - right.Last(), target);
else right = Insert(n, right, target - remainingSum - left.Last(), target);
}
int lefti = 0, righti = right.Count - 1;
while (lefti < left.Count && righti >= 0)
{
int s = left[lefti] + right[righti];
if (s < target) lefti++;
else if (s > target) righti--;
else return true;
}
return false;
}
static List<int> Insert(int num, List<int> nums, int min, int max)
{
var result = new List<int>();
int lefti = 0, left = nums[0]+num;
for (var righti = 0; righti < nums.Count; righti++)
{
int right = nums[righti];
while (left < right)
{
if (min <= left && left <= max) result.Add(left);
left = nums[++lefti] + num;
}
if (right != left && min <= right && right <= max) result.Add(right);
}
while (lefti < nums.Count)
{
left = nums[lefti++] + num;
if (min <= left && left <= max) result.Add(left);
}
return result;
}
This last one solved the problem with 100000 ones in about 5 milliseconds (but this is a best case of the algorithm, with real world data it will be slower).
For your use this algorithm is probably fast enough (and I don't see any obvious improvements). If you enter 10,000 products with a random price between 0 and 20 and your goal is to sum to 500 this is solved in 0.04 seconds on my laptop.
Edit: I just read on Wikipedia that the best known algorithm is O(2^(n/2)*n). This one is O(2^(n/2)). Do I get the Turing Award?