What is the most efficient way to get all combinations?

Question

Possible Duplicate:
Finding all possible combinations of numbers to reach a given sum

Problem

You have a list of people as input, each person has a number of credits. You are given a total that has to be achieved by using one or more persons credits. The function should output all combinations that exist that will result in the total.

For example see below:-

static void Main(string[] args)
{
    int total = Convert.ToInt32(args[0]);
    var persons = new List<Person>();
    persons.Add(new Person { Credits = 10, Name="Steve"});
    persons.Add(new Person { Credits = 5, Name = "Paul" });
    persons.Add(new Person { Credits = 4, Name = "David" });
    persons.Add(new Person { Credits = 1, Name = "Kenneth" });

    PrintAllCombinations(persons, total); // The function in question
}
public class Person
{
    public string Name { get; set; }
    public int Credits { get; set; }
}

In the above example, given a total of 10, the PrintAllCombinations function should output something similar to:-

Combination 1) Steve:10
Combination 2) Paul: 5, David 4, Kenneth 1
Combination 3) Steve: 9, Paul 1
Combination 4) Steve: 5, Paul 5
...etc

UPDATE: I forgot to mention, you can use any part of a persons credits

The example I used is simplified, but the real scenario would be constrained to having no more than a 100 people and the total will always be less than 90.

What is the best solution?

I don't see how this question is specific to C# at all. You only need generic datastructures and some dynamic programming. — hugomg, Jul 21 '11 at 18:35

score 2 · Answer 1 · edited May 23 '17 at 12:04

2

You can read solutions to this ubiquitous problem in Python, Java or Haskell here

Finding all possible combinations of numbers to reach a given sum

Based on your edit specifying that you may take partial credits, you should also look at this post:

generate a list of combinations/sets of numbers with limited supplies

My solution, written in C, is equally applicable to your case.

edited May 23 '17 at 12:04

Community

1
1

answered Jul 21 '11 at 18:22

PengOne

48,188
17
130
149

score 0 · Answer 2 · edited Jul 22 '11 at 18:16

0

Since the backpack problem is NP complete, there isn't an efficient algorithm for this in the general case. However, since the number of credits is small, you can use dynamic programming memoising the following function:

F(N, W) := can we add up to W, using only the first N people?

F(0, 0) = True
F(0, _) = False
F(N, W) = F(N-1, W) || F(N-1, W-w[N])

edited Jul 22 '11 at 18:16

Lance Roberts

22,383
32
112
130

answered Jul 21 '11 at 18:40

hugomg

68,213
24
160
246

What is the most efficient way to get all combinations?

2 Answers2