用于计算不同可能组合的 C# 算法

Question

我有 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

<强>更多细节
解决方案是一组方框 A、方框 B 和方框 C，根据该组方框具有最高排名。每个盒子只能包含该盒子指定的物品之一。 一个物品就是一个物体，物体有3个属性（硬度、弹性、强度）。每个属性可以有1-100的分数。目标是输入每个属性的权重，然后逻辑将遍历所有项目，并根据每个属性的权重确定排名最高的项目组合。为了便于解释，我为每个项目使用了 3 个属性，但项目可以有大约 10 个不同的属性。

这些项目存储在数据库中，它们有一列表示它们可以进入哪个盒子。所有盒子类型都存储在一个数组中，我可以将这些项目放入通用列表中。任何人都会看到一种简单的方法来做到这一点。

我尝试过执行 10 个嵌套的 foreach，看看是否能找到更简单的方法。嵌套循环将需要许多小时才能运行。每个的嵌套基本上拉出所有组合，然后计算每个组合的排名，并存储排名前 10 的项目组合以进行输出

Answer 1

不确定这是否是您想要的，但根据我从您的问题中可以推断出的信息，使用 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...

Answer 2

这看起来像一个二进制程序，其中

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，以查看符号）

这可以使用分支定界进行优化，其步骤比评估每个组合要少得多。

Answer 3

听起来您只需要从每个盒子中获取“最佳”项目，因为将每组中最佳项目的分数相加将得到最佳的总分。如果是这样，您应该能够通过适当的查询在数据库中完成这一切，或者根据需要在客户端通过简单的 LINQ 到对象查询来完成这一切。由于我不是 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 查询中的计算列，然后您可以按框分组，其中 Score = max(score) 和直接从数据库获取结果。

Answer 4

我使用了优秀的 C# 库来进行排列和组合。

它为此类问题提供了有效的算法。