1

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

4 回答 4

1

听起来您只需要从每个盒子中获得“最佳”项目，因为将每个组中最佳项目的分数相加将给出最佳的总体总数。如果是这样，您应该能够在数据库中通过一个体面的查询或在客户端的一个简单的 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)直接从数据库中获取结果。

于 2010-05-18T03:24:44.590 回答
0

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

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

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

于 2011-05-15T20:02:14.917 回答
0

我使用了一个出色的 C# 库来进行排列和组合。

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

于 2010-04-22T23:18:57.837 回答
0

不确定这是否是您正在寻找的内容，但根据我从您的问题中可以推断出的内容，使用 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...

于 2010-04-23T14:20:18.433 回答