我必须实现背包问题的以下变体。背包的每个物品都有优先级和重量。现在我指定一个权重 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;
}
}