C # algorithm for determining various possible combinations

Question

I have 10 boxes, each box can contain one item from a group / item type, each group type is suitable only in one of 10 types of boxes. An element pool can have n number of elements. Groups have completely different elements. Each item has a price, I want an algorithm that will generate all the different features, so I can define different price points and an individual ranking / weight for each element based on the attributes of the element.

so a smaller picture of the problem

BOX A - May contain an element 1,2,3,4

BOX B - may have clause 6,7,8,9,10,11,12

BOX C - may have an element 13,15,16,20,21

Read more The
solution will be the BOX A, BOX B and BOX C set, which has the highest rank based on the set of boxes. Each box can contain only ONE of the assigned items for this field. An element is an object, an object has 3 attributes (hardness, elasticity, strength). Each attribute can have 1-100 points. The goal is to enter a weight for each attribute, then the logic will go through ALL the elements and determine the highest position combinations based on the weights for each attribute. I used 3 attributes for each element for ease of explanation, but elements can have about 10 different attributes.

db, , , . , . .

10 foreach, , . . , 10-

Answer 1

# .

.

Answer 2

, , , , , LINQ . , :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    public class Box
    {
        public string Id { get; set; }
        public List<Item> Items {get;set;}
    }

    public class Item
    {
        public int Id { get; set; }

        public int Firmness { get; set; }
        public int Elasticity { get; set; }
        public int Strength { get; set; }
        public double Price { get; set; }

        public int FirmnessWt { get; set; }
        public int ElasWt { get; set; }
        public int StrWt { get; set; }

        public int ItemScore
        {
            get
            {
                return
                    (Firmness * FirmnessWt) +
                    (Elasticity * ElasWt) +
                    (Strength * StrWt);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // set the rankings
            int firmnessWt = 20;
            int elasWt = 40;
            int strWt = 80;

            // generate the items
            Item item1 = new Item { Id = 1, Elasticity = 1, Firmness = 4, Strength = 2, ElasWt=elasWt, FirmnessWt=firmnessWt, StrWt=strWt };
            Item item2 = new Item { Id = 2, Elasticity = 2, Firmness = 3, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item3 = new Item { Id = 3, Elasticity = 3, Firmness = 2, Strength = 1, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item4 = new Item { Id = 4, Elasticity = 4, Firmness = 1, Strength = 3, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };

            Item item6 = new Item { Id = 6, Elasticity = 1, Firmness = 5, Strength = 2, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item7 = new Item { Id = 7, Elasticity = 1, Firmness = 4, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item8 = new Item { Id = 8, Elasticity = 1, Firmness = 3, Strength = 1, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item9 = new Item { Id = 9, Elasticity = 2, Firmness = 2, Strength = 3, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item10 = new Item { Id = 10, Elasticity = 2, Firmness = 3, Strength = 2, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item11 = new Item { Id = 11, Elasticity = 2, Firmness = 2, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item12 = new Item { Id = 12, Elasticity = 3, Firmness = 6, Strength = 1, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };

            Item item13 = new Item { Id = 13, Elasticity = 3, Firmness = 5, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item15 = new Item { Id = 15, Elasticity = 2, Firmness = 4, Strength = 5, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item16 = new Item { Id = 16, Elasticity = 3, Firmness = 2, Strength = 5, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item20 = new Item { Id = 20, Elasticity = 3, Firmness = 1, Strength = 7, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item21 = new Item { Id = 21, Elasticity = 3, Firmness = 1, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };

            // populate the 3 boxes with the generated items
            List<Box> boxes = new List<Box>
            {
                new Box
                {
                    Id = "A",
                    Items = new List<Item> { item1, item2, item3, item4 }
                },
                new Box
                {
                    Id="B",
                    Items = new List<Item> { item6, item7, item8, item9, item10, item11, item12 }
                },
                new Box
                {
                    Id="C",
                    Items = new List<Item> { item13, item15, item16, item20, item21 }
                }
            };

            // calculate top candidate for firmness
            List<Item> items = boxes.SelectMany(c => c.Items).ToList();

            Item firmnessCandidate = items.OrderByDescending(a => a.Firmness).First();

            // calculate top candidate for elasticity
            Item elasticityCandidate = items.OrderByDescending(b => b.Elasticity).First();


            // calculate top candidate for strength
            Item strengthCandidate = items.OrderByDescending(c => c.Strength).First();

            // calculate top candidate by combined weight
            Item weightCandidate = items.OrderByDescending(w => w.ItemScore).First();

            Console.WriteLine("Firmness - id:" + firmnessCandidate.Id.ToString() + ", score: " + firmnessCandidate.Firmness.ToString());
            Console.WriteLine("Elasticity - id:" + elasticityCandidate.Id.ToString() + ", score: " + elasticityCandidate.Elasticity.ToString());
            Console.WriteLine("Strength - id:" + strengthCandidate.Id.ToString() + ", score: " + strengthCandidate.Strength.ToString());
            Console.WriteLine("Item score - id:" + weightCandidate.Id.ToString() + ", score: " + weightCandidate.ItemScore.ToString());

            Console.ReadLine();
        }
    }
}

...

Answer 3

, "" , . , LINQ-to-objects , . SQL, . Item:

public static double Score<T>(T item, IEnumerable<Weighting<T>> weights)
{
    return weights.Aggregate(0.0, (p, w) => p + w.Apply(item));
}

public static T MaxBy<T>(this IEnumerable<T> items, Func<T, double> selector)
{
    double curMax = double.MinValue;
    T curItem = default(T);
    foreach (T i in items)
    {
        double curValue = selector(i);
        if (curValue > curMax) 
        {
            curMax = curValue;
            curItem = i;
        }
    }
    return curItem;
}

public class Weighting<T>
{
    public Weighting(double weight, Func<T, double> attributeSelector)
    {
        _weight = weight;
        _attributeSelector = attributeSelector;
    }

    private readonly double _weight;
    private readonly Func<T, double> _attributeSelector;

    public double Apply(T item) { return _weight * _attributeSelector(item); }
}

Weighting<Item>[] weights = {new Weighting<Item>(1, i => i.Elasticity),
                             new Weighting<Item>(2, i => i.Firmness),
                             new Weighting<Item>(.5, i => i.Strength)};

var hsQuery = from i in allItems
              group i by i.Box into boxItems
              select boxItems.MaxBy(bi => Score(bi, weights));

I assume that a reasonable way to make a weighted score is a calculated column in an SQL query, which you can then group by box where score = max(score)get the result directly from the database.

Answer 4

It looks like a binary program where

maximize $\sum_i c_i x_i$ (value function)


$x_i \in \{ 0, 1 \} \forall i$ (binary constraint)

$x_1 + x_2 + x_3 + x_4 = 1$ (exactly one item in box a constraint)

$x_6 + x_7 + x_8 + x_9 + x_{10} + x_{11} + x_{12} = 1$

$x_{13} + x_{15} + x_{16} + x_{20} + x_{21} = 1$

$\sum_i p_i x_i <= P$ (price constraint)

(paste above into the LaTeX evaluator, e.g. math.se to see the characters)

This can be optimized by branching and linking with far fewer steps than evaluating each combination.