1

私は 10 個のボックスを持っています。各ボックスは、アイテムのグループ/タイプから 1 つのアイテムを保持できます。各「グループ」タイプは、10 個のボックス タイプの 1 つにのみ収まります。アイテム プールには n 個のアイテムを含めることができます。グループには完全に異なる項目があります。各アイテムには価格があります。さまざまな可能性をすべて生成するアルゴリズムが必要なので、アイテムの属性に基づいて、各アイテムへのカスタム ランク/重量の割り当てに対して、さまざまな価格ポイントを把握できます。

問題の小さな図

ボックス A - アイテム 1、2、3、4 を入れることができます

ボックス B - アイテム 6、7、8、9、10、11、12 を持つことができます

ボックス C - アイテム 13、15、16、20、21 を持つことができます

詳細
ソリューションは、BOX A、BOX B、および BOX C のセットであり、ボックスのセットに基づいて最大のランクを持ちます。各ボックスには、そのボックスに指定されたアイテムを 1 つだけ入れることができます。アイテムはオブジェクトであり、オブジェクトには 3 つの属性 (固さ、弾力性、強さ) があります。各属性のスコアは 1 ～ 100 です。目標は、各属性の重みを入力することです。次に、ロジックがすべてのアイテムに対して実行され、各属性の重みに基づいて上位ランクのアイテムの組み合わせが決定されます。説明を簡単にするために各アイテムに 3 つの属性を使用しましたが、アイテムには約 10 の異なる属性があります。

アイテムはデータベースに保存され、どのボックスに入ることができるかを示す列があります。すべてのボックスの種類は配列に保存され、アイテムを一般的なリストに入れることができます。誰もがこれを行う簡単な方法を見ています。

より簡単な方法を見つけることができるかどうかを確認するために、10 個のネストされた foreach を実行してみました。ネストされたループの実行には何時間もかかります。ネストされた for each は基本的にすべての組み合わせをプルし、各組み合わせのランクを計算し、上位 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));

group by box where score = max(score)加重スコアをSQLクエリの計算列にして、データベースから直接結果を取得できる賢い方法があると思います。

于 2010-05-18T03:24:44.590 に答える
0

Not sure if this was what you were looking for, but based on what I can infer from your question, using LINQ will be a lot simpler to code. Here's my guesstimate of what the answer should be:

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 に答える
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)

(上記を math.se などの LaTeX エバリュエーターに貼り付けて、シンボルを表示します)

これは、すべての組み合わせを評価するよりもはるかに少ない手順で、分岐限定を使用して最適化できます。

于 2011-05-15T20:02:14.917 に答える
0

順列と組み合わせ論には優れた C# ライブラリを使用しました。

このクラスの問題に対して効率的なアルゴリズムを提供します。

于 2010-04-22T23:18:57.837 に答える