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

What you're looking is solution for knapsack problem. There is no known way to do it fast. You can modify dynamic solution (https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem) to choose at most maxCount items like this:

public static List<Item> BestCombination(List<Item> items, int maxPrice, int maxCount)
{
    var scores = new int[items.Count + 1, maxPrice + 1, maxCount + 1];

    for (int i = 1; i <= items.Count; i++)
    {
        var item = items[i - 1];
        for (int count = 1; count <= Math.Min(maxCount, i); count++)
        { 
            for (int price = 0; price <= maxPrice; price++)
            {                    
                if (item.Price > price)
                    scores[i, price, count] = scores[i - 1, price, count];                
                else
                    scores[i, price, count] = Math.Max(
                        scores[i - 1, price, count],
                        scores[i - 1, price - item.Price, count - 1] + item.Score);
            }
        }
    }

    var choosen = new List<Item>();
    int j = maxPrice;
    int k = maxCount;
    for (int i = items.Count; i > 0; i--)
    {
        var item = items[i - 1];
        if (scores[i, j, k] != scores[i - 1, j, k])
        {
            choosen.Add(item);
            j -= item.Price;
            k--;
        }
    }            

    return choosen;
}

Keep in mind that choosing exaclty maxCount objects can give you lower total score than choosing <= maxCount objects. Eg for items [(100, 10), (200,20), (300,30), (500,80)], maxPrice = 500 and maxCount = 2 this method returns only (500,80). If you want it to return [(200,20), (300,30)], you can initialize array like this:

for (int i = 0; i <= items.Count; i++)
{
    for (int price = 0; price <= maxPrice; price++)
    {
        for (int count = 1; count <= maxCount; count++)
        {
            scores[i, price, count] = int.MinValue;
        }
    }
}

to make sure that in scores[, , count] are sums of count scores (or MinValue). However, it still can return another number of items if there is no way to choose exactly maxCount.

Answer 2

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