Алгоритм C # для определения различных возможных комбинаций - PullRequest
Новая
       17

Алгоритм C # для определения различных возможных комбинаций

1 голос
/ 23 апреля 2010

У меня есть 10 ящиков, каждый из которых может содержать один предмет из группы / типа предметов, каждый тип «группы» подходит только для одного из 10 типов ящиков. В пуле предметов может быть n предметов. У групп есть совершенно разные предметы. У каждого предмета есть цена, мне нужен алгоритм, который будет генерировать все различные возможности, чтобы я мог вычислять разные ценовые баллы по сравнению с пользовательским присвоением ранга / веса на основе атрибутов предмета.

так что меньшая картина проблемы

BOX A - может содержать элемент 1,2,3,4

BOX B - может иметь элемент 6,7,8,9,10,11,12

BOX C - может иметь элемент 13,15,16,20,21

Подробнее
Решением будет набор BOX A, BOX B и BOX C, имеющий наибольший ранг на основе набора блоков. Каждый ящик может содержать только ОДИН из назначенных предметов для этого ящика. Предмет - это объект, объект имеет 3 атрибута (твердость, эластичность, прочность). Каждый атрибут может иметь 1-100 для оценки. Цель состоит в том, чтобы ввести вес для каждого атрибута, тогда логика будет проходить через ВСЕ элементы и определять комбинации элементов с наивысшим рейтингом на основе весов для каждого атрибута. Для простоты объяснения я использовал 3 атрибута для каждого элемента, но элементы могут иметь около 10 различных атрибутов.

Элементы хранятся в БД, у них есть столбец, в котором указано, в какой блок они могут входить. Все типы блоков хранятся в массиве, и я могу поместить элементы в общий список. Любой видит простой способ сделать это.

Я попытался сделать 10 вложенных foreach'ов, чтобы посмотреть, смогу ли я найти более простой способ. Вложенные циклы займут МНОГО часов. вложенные для каждой из них, в основном, вытягивают все комбинации, затем вычисляют ранг для каждой комбинации и сохраняют топ-10 ранжированных комбинаций элементов для вывода

Ответы [ 4 ]

0 голосов
/ 16 мая 2011

Это похоже на двоичную программу, где 

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)

(вставьте вышеупомянутое в оценщик LaTeX, например math.se, чтобы увидеть символы)

Это можно оптимизировать, используя ветвление и связывание, за гораздо меньшее количество шагов, чем оценка каждой комбинации.

0 голосов
/ 23 апреля 2010

Не уверен, что это именно то, что вы искали, но исходя из того, что я могу вывести из вашего вопроса, использование 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();
        }
    }
}

HTH ...

0 голосов
/ 18 мая 2010

Похоже, вам просто нужно получить «лучший» предмет из каждой коробки, так как сложение баллов за лучший предмет в каждой группе даст наилучшую общую сумму.Если это так, вы сможете сделать все это в базе данных с помощью приличного запроса или с помощью простого запроса 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));

Я предполагаю, что есть умный способ сделать взвешенный счет вычисляемым столбцом в запросе SQL, который затем можно group by box where score = max(score) и получить результат непосредственно избаза данных.

0 голосов
/ 23 апреля 2010

Я использовал выдающуюся библиотеку C # для перестановок и комбинаторики.

Предоставляет эффективные алгоритмы для этого класса задач.

...