ナップザック問題の次のバリエーションを実装する必要があります。ナップザックの各アイテムには、優先度と重量があります。次に、重み 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;
}
}