Selecting items from a list to achieve the amount

Question

I have a list of elements with numerical values, and I need to get the sum using these elements. I need your help to create such an algorithm. Below is an example that describes my problem written in C #:

int sum = 21; List<Item> list = new List<Item>(); list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 }); list.Add(new Item() { Id = Guid.NewGuid(), Value = 5 }); list.Add(new Item() { Id = Guid.NewGuid(), Value = 12 }); list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 }); list.Add(new Item() { Id = Guid.NewGuid(), Value = 2 }); list.Add(new Item() { Id = Guid.NewGuid(), Value = 7 }); List<Item> result = // the items in the list that has the defined sum. 

Note. I have no limit on the number of items in the result.

Answer 1

This is called the problem of the sum of the subset and is considered a complex problem in computer science. Not difficult, how difficult, but difficult to do quickly - you can easily write an algorithm to do this, but for significant inputs it will easily take billions of years.

If you are happy with the slow solution, which is practically possible for small inputs, try something like this:

• Generate all subsets of the input list.

• For each subset, we compute the sum of the elements in this subset.

• Returns the first subset for which the sum matches.

Here is a method that returns all subsets (in fact, subsequences, since it maintains the order of the elements, although this does not matter in your case):

 /// <summary> /// Returns all subsequences of the input <see cref="IEnumerable&lt;T&gt;"/>. /// </summary> /// <param name="source">The sequence of items to generate /// subsequences of.</param> /// <returns>A collection containing all subsequences of the input /// <see cref="IEnumerable&lt;T&gt;"/>.</returns> public static IEnumerable<IEnumerable<T>> Subsequences<T>( this IEnumerable<T> source) { if (source == null) throw new ArgumentNullException("source"); // Ensure that the source IEnumerable is evaluated only once return subsequences(source.ToArray()); } private static IEnumerable<IEnumerable<T>> subsequences<T>(IEnumerable<T> source) { if (source.Any()) { foreach (var comb in subsequences(source.Skip(1))) { yield return comb; yield return source.Take(1).Concat(comb); } } else { yield return Enumerable.Empty<T>(); } } 

So now you can write something like this ...

 var result = list.Subsequences() .FirstOrDefault(ss => ss.Sum(item => item.Value) == sum); 

Answer 2

This is called the problem of the sum of the subset, with the modification - that you do not want to get to zero, but to a certain number.

Here the wiki has to say about it - http://en.wikipedia.org/wiki/Subset_sum_problem .

You might think of some optimizations to suit your domain knowledge. For example, if the largest number + the lowest number is greater than the sum →, then the largest number will never be used, and you can exclude it (and try to do the same for the new highest number ..).

I remember doing it, as Samuel suggested - a recursive path that wasn't so scary (but of course there is always a stackoverflow problem ...).

Answer 3

recursive, add items until A) you reach the sum or B) you get too much if you finish, if B you change the elements trying to use all possible configurations. Maybe prevent the system from adding an item if the current item is already larger than the last item that went over the sum

Answer 4

I'm not quite sure what kind of sun you are here. If you want the sum of all values ​​to be combined, use this code:

 int result = list.Sum( i => i.Value); 

If you want all elements to have a specific value, use this code:

 int x = 3; List<Item> result = list.Where( i => i.Value == x);