Java组合优化

-1

我有一个组合优化问题。Java组合优化

我有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帮助我识别出价。

来源

2015-11-13 Daniel

因此除了头痛之外，还有什么问题？ – redFIVE

那么我不知道如何解决这个任务。 – Daniel

问问你的教授，然后再回来一个具体的问题 – redFIVE

有一个非常明显的方法：尝试每个子集。当你有30件物品时，这并不是很好，因此，如果你不介意等一会儿，那就没问题了。这不是需要几个月的事情。

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

技术＃1，从搜索空间修剪无用的树。如果您将搜索组织为一个隐含的二叉树，它会为每个项目做出“我会不会采取或不采取”的选择，那么在您完全处于最底层之前，您可以决定的子树是无意义的。最简单的方法就是将所有项目的权重总和设置为您暂时选择的项目的总和，如果这比迄今为止找到的最便宜的解决方案要多，那么稍后它不会改进（假设您没有负价格，你不这样做，因为如果有任何负价格，那么你只要把它们全部拿走，然后在这个搜索中不包括它们）。仅此一项就可能会产生很大的影响。

技术＃2，避免死角。如果剩下的只有1个出价没有包含某一行（如果有的话，其他所有出价都暂定为不包括在内），那么没有什么可以决定的，您必须拿去。这当然可以迫使成本高于最好的成本，见＃1。

技术＃3，使用可接受的启发式来修剪更多。例如，一个微不足道的：说某行还没有被覆盖。显然，为了产生一个解决方案，它必须被覆盖，所以在决定是否修剪这个分支之前，可以将最便宜的方法添加到运行总数中。不过，您不能只为所有未被覆盖的行添加所有最低成本的总和，因为相同的出价可能会覆盖其中的几个，但如果您采用最大值而不是总和，则它将起作用。这里有更好的技巧，但这个很简单。

来源

2015-11-13 21:13:19 harold

非常感谢您的工作。这绝对帮助了我很多。 – Daniel

Java组合优化

回答

相关问题