C# - Combinatorics

Question

I have a list of ~300 objects which all have a price and a score. I need to find the best combination (i.e. highest total score) of 15 of those objects whose total price is less than X.

The most straightforward way to do this, as I see it, is to nest 15 for loops and check every possible combination, but that would take days.

Is there any 'clean' way to do this in C#?

Thanks!

Answer 1

It is difficult to help without an example, but if I understand the problem then this might help.

Assuming your object looks like this

public class Item
{
        public int Score { get; set; }
        public decimal Price { get; set; }
}

Then the following should sort you out.

var listOfObjects = new List<Item>();

var topItems = listOfObjects.Where(p => p.Price < 100).OrderByDescending(p => p.Score).Take(15);

EDIT : After all details was disclosed, the following should help

DISCLAIMER : Quick and dirty solution (sub optimal)

Create a new class

public class ItemWithRunningTotal
{
    public Item Item { get; set; }
    public decimal RunningTotal { get; set; }
}

Then the following should get you what you need.

var maxTotal = 1500; //for you 8000
        var objects = new List<Item>()
                      {
                          new Item() {Score = 10, Price = 100},
                          new Item() {Score = 20, Price = 800},
                          new Item() {Score = 40, Price = 600},
                          new Item() {Score = 5, Price = 300},
                      };

        decimal runningTotal = 0;
        var newList = objects
            .OrderByDescending(p => p.Score)
            .Select(p =>
                    {
                        runningTotal = runningTotal + p.Price;
                        return new ItemWithRunningTotal()
                               {
                                   Item = p,
                                   RunningTotal = runningTotal
                               };
                    })
            .OrderByDescending(p => p.RunningTotal)
            .Where(p => p.RunningTotal <= maxTotal).Take(15);