C# - Combinatorics

Question

Her biri bir fiyatı ve puanı olan ~ 300 nesnenin bir listesine sahibim. Toplam fiyatı X'den daha az olan bu nesnelerin en iyi kombinasyonunu (yani en yüksek toplam skoru) bulmalıyım.

Bunu yapmanın en basit yolu, döngüler ve Her olası kombinasyonu kontrol edin, ancak bu günler alır.

C# içinde bunu yapmak için 'temiz' bir yolu var mı?

Teşekkürler!

Answer 1

Örnek olmadan yardımcı olmak zordur, ancak sorunu anlarsam bu yardımcı olabilir.

Objenizi varsayarsak Sonra şu dışarı sıralamak gereken bu

public class Item 
{ 
     public int Score { get; set; } 
     public decimal Price { get; set; } 
} 

benziyor.

var listOfObjects = new List<Item>(); 

var topItems = listOfObjects.Where(p => p.Price < 100).OrderByDescending(p => p.Score).Take(15); 

DÜZENLEME: tüm ayrıntılar açıklanmasının ardından ise aşağıdaki

FERAGATNAMEYİ yardımcı olmalıdır: Hızlı ve kirli çözüm (sub optimal)

yeni bir sınıf oluşturmak

public class ItemWithRunningTotal 
{ 
    public Item Item { get; set; } 
    public decimal RunningTotal { get; set; } 
} 

Sonra aşağıdakiler ihtiyacınız olanı almalı.

var maxTotal = 1500; //for you 8000 
     var objects = new List<Item>() 
         { 
          new Item() {Score = 10, Price = 100}, 
          new Item() {Score = 20, Price = 800}, 
          new Item() {Score = 40, Price = 600}, 
          new Item() {Score = 5, Price = 300}, 
         }; 

     decimal runningTotal = 0; 
     var newList = objects 
      .OrderByDescending(p => p.Score) 
      .Select(p => 
        { 
         runningTotal = runningTotal + p.Price; 
         return new ItemWithRunningTotal() 
           { 
            Item = p, 
            RunningTotal = runningTotal 
           }; 
        }) 
      .OrderByDescending(p => p.RunningTotal) 
      .Where(p => p.RunningTotal <= maxTotal).Take(15); 

Answer 2

Aradığınız şey sırt çantası problemi için bir çözümdür. Bunu hızlı yapmanın bilinen bir yolu yoktur. Böyle en fazla maxCount öğeleri seçmek için dinamik bir çözüm (https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem) değiştirebilirsiniz:

public static List<Item> BestCombination(List<Item> items, int maxPrice, int maxCount) 
{ 
    var scores = new int[items.Count + 1, maxPrice + 1, maxCount + 1]; 

    for (int i = 1; i <= items.Count; i++) 
    { 
     var item = items[i - 1]; 
     for (int count = 1; count <= Math.Min(maxCount, i); count++) 
     { 
      for (int price = 0; price <= maxPrice; price++) 
      {      
       if (item.Price > price) 
        scores[i, price, count] = scores[i - 1, price, count];     
       else 
        scores[i, price, count] = Math.Max(
         scores[i - 1, price, count], 
         scores[i - 1, price - item.Price, count - 1] + item.Score); 
      } 
     } 
    } 

    var choosen = new List<Item>(); 
    int j = maxPrice; 
    int k = maxCount; 
    for (int i = items.Count; i > 0; i--) 
    { 
     var item = items[i - 1]; 
     if (scores[i, j, k] != scores[i - 1, j, k]) 
     { 
      choosen.Add(item); 
      j -= item.Price; 
      k--; 
     } 
    }    

    return choosen; 
} 

aklınızda tutun maxCount nesneleri <= maxCount nesneleri seçmek yerine size daha düşük toplam puan verebilir exaclty seçmek. Örneğin [(100, 10), (200,20), (300,30), (500,80)], maxPrice = 500 ve maxCount = 2 öğeleri için bu yöntem sadece döner (500,80). Eğer, sen başlatabilir dizi şöyle [(300,30), (200,20)] geri dönmek isterseniz:

for (int i = 0; i <= items.Count; i++) 
{ 
    for (int price = 0; price <= maxPrice; price++) 
    { 
     for (int count = 1; count <= maxCount; count++) 
     { 
      scores[i, price, count] = int.MinValue; 
     } 
    } 
} 

yılında scores[, , count]count puanları (veya MinValue) toplamından oluşmasıdır emin olmak için. Bununla birlikte, tam olarak maxCount'u seçmenin bir yolu yoksa, başka bir sayıda öğe döndürebilir.