Java組合優化

Question

我有一個組合優化問題。

我有X個出價包含價格和n行。價格是這n行的總價格。 n可以在1到12之間。所有的行都有一個數字（1-12）。這意味着總共有12個不同的行。出價不能有兩次相同的行。我可以接受出價或拒絕出價。不可能以某種方式將投標分爲兩個（或更多）。

現在我有一個長度爲12位的位數組，如果我需要那行，它會告訴我每一行。

我想要的是爲我需要的行計算最便宜的可能分配。頭痛，我目前無法解決這個問題。也許你們中的一個能夠幫助我一點。

這裏我簡單Bid類：

public class Bid { 
    private int price; 
    private int[] rows; // e.g. rows[0] = 3 means this bid contains row 3 
    private int connectionID; 

    public Bid(int price, int[] rows, int connectionID) { 
     super(); 
     this.price = price; 
     this.rows = rows; 
     this.connectionID = connectionID; 
    } 

    public int getPrice() { 
     return price; 
    } 

    public int[] getRows() { 
     return rows; 
    } 

    public int getConnectionID() { 
     return connectionID; 
    } 
} 

非常感謝！

Ps .: ConnectionID幫助我識別出價。

Answer 1

有一個非常明顯的方法：嘗試每個子集。當你有30件物品時，這並不是很好，因此，如果你不介意等一會兒，那就沒問題了。這不是需要幾個月的事情。

但我們可以做得更好，至少在平均水平上。

技術＃1，從搜索空間修剪無用的樹。如果您將搜索組織爲一個隱含的二叉樹，它會爲每個項目做出「我會不會採取或不採取」的選擇，那麼在您完全處於最底層之前，您可以決定的子樹是無意義的。最簡單的方法就是將所有項目的權重總和設置爲您暫時選擇的項目的總和，如果這比迄今爲止找到的最便宜的解決方案要多，那麼稍後它不會改進（假設您沒有負價格，你不這樣做，因爲如果有任何負價格，那麼你只要把它們全部拿走，然後在這個搜索中不包括它們）。僅此一項就可能會產生很大的影響。

技術＃2，避免死角。如果剩下的只有1個出價沒有包含某一行（如果有的話，其他所有出價都暫定爲不包括在內），那麼沒有什麼可以決定的，您必須拿去。這當然可以迫使成本高於最好的成本，見＃1。

技術＃3，使用可接受的啓發式來修剪更多。例如，一個微不足道的：說某行還沒有被覆蓋。顯然，爲了產生一個解決方案，它必須被覆蓋，所以在決定是否修剪這個分支之前，可以將最便宜的方法添加到運行總數中。不過，您不能只爲所有未被覆蓋的行添加所有最低成本的總和，因爲相同的出價可能會覆蓋其中的幾個，但如果您採用最大值而不是總和，則它將起作用。這裏有更好的技巧，但這個很簡單。