我有不同类别的物品。每个物品都有价值和重量。
例如:
ClassA: [A1, A2, A3]
ClassB: [B1, B2, B3]
ClassC: [C1, C2, C3]
我应该如何修改经典的0-1背包问题,以便算法优化解决方案,最大化总体价值,考虑所有类别中的物品,但只允许从一个类别中选择最多一个物品?
例如:
ClassA: [A1, A2, A3]
ClassB: [B1, B2, B3]
ClassC: [C1, C2, C3]
我应该如何修改经典的0-1背包问题,以便算法优化解决方案,最大化总体价值,考虑所有类别中的物品,但只允许从一个类别中选择最多一个物品?
package knapsack;
import java.util.ArrayList;
import java.util.List;
public class Knapsack {
private int totalNumberOfItems;
private int maxmimumKnapsackCapacityUnits;
private double[][] optimum;
private boolean[][] solution;
private double [] value;
private int [] weight;
public Knapsack(int knapsackCapacityUnits, List<KnapsackItem> items){
this.totalNumberOfItems = items.size();
this.maxmimumKnapsackCapacityUnits = knapsackCapacityUnits;
this.optimum = new double[items.size() + 1][knapsackCapacityUnits + 1];
this.solution = new boolean[items.size() + 1][knapsackCapacityUnits + 1];
this.value = new double[items.size() + 1];
this.weight = new int[items.size() + 1];
int index=1;
for(KnapsackItem item : items){
value[index] = item.value;
weight[index] = item.weight;
index++;
}
}
public List<KnapsackItem> optimize(){
for(int currentItem = 1; currentItem <= totalNumberOfItems; currentItem++){
for(int currentWeightUnit = 1; currentWeightUnit <= maxmimumKnapsackCapacityUnits; currentWeightUnit++){
double option1 = optimum[currentItem - 1][currentWeightUnit];
double option2 = Integer.MIN_VALUE;
if(weight[currentItem] <= currentWeightUnit){
option2 = value[currentItem] + optimum[currentItem-1][currentWeightUnit - weight[currentItem]];
}
optimum[currentItem][currentWeightUnit] = Math.max(option1, option2);
solution[currentItem][currentWeightUnit] = (option2 > option1);
}
}
boolean take [] = new boolean[totalNumberOfItems + 1];
for(int currentItem = totalNumberOfItems,
currentWeightUnit = maxmimumKnapsackCapacityUnits;
currentItem > 0; currentItem --){
if(solution[currentItem][currentWeightUnit]){
take[currentItem] = true;
currentWeightUnit = currentWeightUnit - weight[currentItem];
}
else{
take[currentItem] = false;
}
}
List<KnapsackItem> items = new ArrayList<KnapsackItem>();
for(int i = 0; i < take.length; i++){
KnapsackItem newItem = new KnapsackItem();
newItem.value = value[i];
newItem.weight = weight[i];
newItem.isTaken = take[i];
items.add(newItem);
}
return items;
}
}
谢谢!
if w is achievable with maximum value v:
但这是在您遍历类项之前发生的。所以我不确定这应该如何工作。我已经包含了我的代码,也许我的算法有点不同,您可以看一下我做了什么。谢谢! - Wild Goat