다른 가능한 조합을 찾기위한 C# 알고리즘

Question

10 개의 상자가 있으며 각 상자에는 항목/그룹 유형의 항목 하나를 저장할 수 있으며 각 '그룹'유형은 10 개의 상자 유형 중 하나에 맞습니다. 항목 풀은 n 개의 항목을 가질 수 있습니다. 그룹에는 완전히 다른 항목이 있습니다. 각 항목은 가격이 있습니다. 나는 모든 다른 가능성을 생성하는 알고리즘을 원합니다. 따라서 항목 속성에 따라 각 항목에 대해 다른 가격대 대 사용자 지정 순위/가중치를 계산할 수 있습니다. -6,7,8,9- 항목을 가질 수있다 -

때문에 문제

BOX (A)의 작은 포토 - 그것은

박스에 상품 B는 1,2,3,4 수 10,11,12

BOX C - 항목을 13,15,16,20,21

자세한 내용을 가질 수
,536,913,632 솔루션은 BOX A, BOX B 및 BOX C의 집합이며 상자 집합을 기준으로 가장 큰 순위를가집니다. 각 상자는 해당 상자에 지정된 항목 중 하나만 포함 할 수 있습니다. 항목은 객체이며, 객체는 3 가지 속성 (견고성, 탄성, 강도)을 갖습니다. 각 속성은 점수에 1-100을 가질 수 있습니다. 목표는 각 속성에 대한 가중치를 입력하는 것입니다. 그런 다음 논리는 ALL 항목을 통해 실행되며 각 속성의 가중치에 따라 최상위 순위 항목 조합을 결정합니다. 설명을 쉽게하기 위해 각 항목마다 3 가지 속성을 사용했지만 항목에는 약 10 가지 속성이 있습니다.

항목은 DB에 저장되며, 입력 할 수있는 상자를 나타내는 열이 있습니다. 모든 상자 유형은 배열에 저장되며 항목을 일반 목록에 넣을 수 있습니다. 누구나 쉽게이 작업을 수행 할 수 있습니다.

나는 간단한 방법을 찾을 수 있는지보기 위해 10 개의 중첩 된 foreach를 시도했다. 중첩 된 루프는 실행하는 데 많은 시간이 걸립니다. 중첩 된 모든 조합은 기본적으로 모든 조합을 가져온 다음 각 조합에 대한 순위를 계산하고 상위 10 위의 항목 조합을 출력에 저장합니다.

Answer 1

순열 및 조합에 대해 outstanding C# library을 사용했습니다.

이 클래스는 효율적인 알고리즘을 제공합니다.

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(); 
     } 
    } 
} 

HTH ... 그것은 당신이 바로 최고의 항목의 점수를 추가하는 등, 각 상자에서 "최고"항목을 얻을 필요가 같은 소리

Answer 3

: 여기에 대답은 무엇을해야 내 어디 까지나 추정치 일뿐 정확한 통계입니다 각 그룹에서 가장 좋은 전체 합계를 줄 것입니다. 그렇다면 괜찮은 쿼리를 사용하거나 원하는 경우 클라이언트 측에서 간단한 LINQ- 개체 쿼리를 사용하여 데이터베이스에서이 모든 작업을 수행 할 수 있어야합니다. 저는 SQL 사용자가 아니기 때문에 클라이언트 접근 방식으로 갈 것입니다. 항목 클래스에 대한 분명한 정의를 사용 :

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 쿼리에서 계산 된 열 수 있도록하는 영리한 방법이있다.

Answer 4

이

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 같은 라텍스 평가자에 상기 붙여) 이진 프로그램 같다 모든 조합을 평가하는 것보다 훨씬 적은 단계로