What is the most efficient way to get all combinations? [duplicate]

This question already has answers here: Closed 11 years ago.

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 sh开发者_Python百科ould 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?

---

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.

---

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])