java - 背包 - 优先级最低，重量最小

Question

我必须实现背包问题的以下变体。背包中的每件元素都有优先级和重量。现在我指定一个权重 X。我必须知道计算权重总和至少为 X 并且具有最低优先级的最小项目集。每个项目只能选择一次。示例:

    KnapsackItem a = new KnapsackItem("a", 1000, 0.1);
    KnapsackItem b = new KnapsackItem("b", 1000, 0.01);
    KnapsackItem c = new KnapsackItem("c", 1000, 0.01);

    Knapsack sack = new Knapsack(1900);
    sack.addItem(a);
    sack.addItem(b);
    sack.addItem(c);

    for (KnapsackItem item : sack.compute()) {
        System.out.println(item);
    }

这应该返回 b,c。

我的解决方案返回 b, a。我不知道为什么。花了几个小时调试，但我就是不明白。也许有人可以看看或发布这个问题变体的解决方案作为代码。

public class Knapsack {
/**
 * The sum of the priorities. For example "prisoSum.get(2) returns 5" means,
 * that element 2 returns a sum priority of 5.
 */
private HashMap<Integer, Double> prioSum = new HashMap<Integer, Double>();

/**
 * List of items.
 */
private ArrayList<KnapsackItem> items;

/**
 * Minimum weight. The sum of the weights of the items in the item list must
 * at least be equal to this value.
 */
private int minWeight;

/**
 * Constructor.
 *
 * @param minWeight
 *            the minimum weight.
 */
public Knapsack(final int minWeight) {
    this.items = new ArrayList<KnapsackItem>();
    this.minWeight = minWeight;
}

/**
 * Computes the items to select.
 *
 * @return list of items to select.
 */
public final ArrayList<KnapsackItem> compute() {
    ArrayList<KnapsackItem> ret = new ArrayList<KnapsackItem>();
    int weightLeft = this.minWeight;
    KnapsackItem item;

    while (weightLeft > 0) {
        ArrayList<KnapsackItem> diff = getDifference(this.items, ret);
        if (diff.size() == 0) {
            break;
        }

        item = computeBestItemForMinVal(diff,
                weightLeft);

        ret.add(item);
        weightLeft -= item.getWeight();
    }

    return ret;
}

/**
 * Gets the best item to select for a given weight.
 *
 * @param list
 *            List of items to select form
 * @param minVal
 *            given weight
 * @return best item from list for given weight
 */
private KnapsackItem computeBestItemForMinVal(
        final ArrayList<KnapsackItem> list, final int minVal) {
    int[] best = new int[minVal + 1];
    for (int w = 0; w <= minVal; w++) {
        for (int i = 0; i < list.size(); i++) {
            KnapsackItem curIt = list.get(i);

            // Current priority inclusive all antecessors
            double curVal = 0;
            if (prioSum.get(w - curIt.getWeight()) != null) {
                curVal = prioSum.get(w - curIt.getWeight())
                        + curIt.getPriority();
            } else {
                curVal = 0 + curIt.getPriority();
            }
            if (prioSum.get(w) == null) {
                prioSum.put(w, curVal);
                best[w] = i;
            } else if (prioSum.get(w) > curVal) {
                prioSum.put(w, curVal);
                best[w] = i;
            }
        }
    }
    return list.get(best[minVal]);
}

/**
 * Computes the difference between two given list of Knapsack items and
 * returns it.
 *
 * @param main
 *            first list
 * @param sub
 *            second list
 * @return difference
 */
private ArrayList<KnapsackItem> getDifference(
        final ArrayList<KnapsackItem> main,
        final ArrayList<KnapsackItem> sub) {
    ArrayList<KnapsackItem> ret = new ArrayList<KnapsackItem>();

    for (int m = 0; m < main.size(); m++) {

        boolean found = false;
        for (int s = 0; s < sub.size(); s++) {
            if (main.get(m).getName() == sub.get(s).getName()) {
                found = true;
                break;
            }
        }

        if (!found) {
            ret.add(main.get(m));
        }
    }

    return ret;
}

}

Answer 1

我发现了我的错误。我必须添加
prioSum.clear();计算 BestItemForMinVal()。这样之前调用的数据就会被删除。我现在还从 1 而不是 0 开始重量的 for 循环:

private KnapsackItem computeBestItemForMinVal(
        final ArrayList<KnapsackItem> list, final int minVal) {
    int[] best = new int[minVal + 1];
    prioSum.clear();
    for (int w = 1; w <= minVal; w++) {
...