Java 组合优化

Question

我有一个组合优化问题。

我有 X 个包含价格和 n 行的出价。价格是这 n 行的总价格。 n 可以介于 1 和 12 之间。所有行都附有一个数字 (1-12)。这意味着总共有 12 行不同的行。出价永远不能在同一行出现两次。我可以接受出价或拒绝出价。不可能以某种方式将出价分成两个（或更多）。

现在我有一个长度为 12 位的位数组，告诉我每一行是否需要该行。

我想要的是为我需要的行计算最便宜的可能分配。头疼我暂时无法解决这个问题。也许你们中的一个可以帮助我一点。

这是我的简单出价 class:

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 个项目并因此有 2³⁰ 个子集时，这不是很好，但如果您不介意稍等一下，那也没关系。这不是需要几个月的时间。

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

技术 #1，从搜索中删除无用的树 space。如果您将搜索组织为隐式二叉树，它为每个项目 "do I take this or not" 做出选择，那么在您一直处于底部之前，您可以确定一些子树是无意义的。最简单的方法就是计算到目前为止您暂时选择采用的所有项目的重量总和，如果这比您迄今为止找到的最便宜的解决方案还多，那么以后就不会改进（假设您没有负价格，你不会这样做，因为如果有任何负价格，那么你只需确定所有这些价格，然后不要将它们包括在此搜索中）。仅这一点就可能已经产生很大的不同。

技巧#2，避免死胡同。如果只剩下 1 个具有您尚未包含的特定行的出价（所有其他，如果有的话，具有该行的出价暂时决定不包括在内），那么没有什么可决定的，您必须拿着。这当然会迫使成本变得高于找到的最佳成本，请参见#1。

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

Java 组合优化

Java Combinatorial optimization

java

knapsack-problem