將項目分組到平衡組

Question

根據每個項目的變量屬性將x項目數量組合到y組中的最佳方式是什麼？重量。

給我留下與每組持有相同金額（價格）（或接近相同）的y組數量。所以這些羣體是通過累積重量來平衡的。

Answer 1

使用java.util.Arrays.sort(Object[] a, Comparator c)，執行Comparator，根據您的要求進行排序。

Answer 2

我們打電話給你的「y金額」bin。您聲明您希望將您的物品分配到所有垃圾箱之間。

一個具有類似屬性的結構是平衡樹。接下來我要做的是以下幾點。首先，使用所選屬性作爲關鍵字填充一棵平衡樹。接下來，下降到樹的期望水平，使得該水平上有N個元素，N是你想要的數量。將來自每個節點的所有元素派生到一個單獨的容器中。

然後，剩下的唯一一件事就是將這個級別上的節點上的元素分配到bin中。只需選擇一個標準來選擇它將要運行的倉庫並應用它。你的箱子應該合理平衡。

Answer 3

我可能會這樣做，的Map索引的屬性。例如：

Map<K, Set<V>> results = new HashMap<K, Set<V>>(); 
for (V item : items) { 
    K key = item.getProperty(); 
    Set<V> group = results.get(key); 
    if (group == null) { 
     group = new HashSet<V>(); 
     results.put(key, group); 
    } 
    group.add(item); 
} 

其中V是您的物品的類型，K是物業的類型。

Answer 4

這是Partition problem推廣到y組而不是2.問題爲y=2是弱NP-硬，所以存在一個僞多項式算法，有效地解決了它，只要權重是小的整數。