我正在尝试生成一个算法，以找到最佳组合的n个项目（在我的情况下是4个），这些项目只能放置在背包中一次（0-1），并且具有最大重量容量。简而言之，我想将不超过四个唯一的项目放入我的背包中，使它们的重量小于某个值W，同时最大化它们的总价值。我的第一次尝试和假设是在多维背包问题中将所有项目体积限制为1，将卷限制为4。但我遇到了一个问题，它不是0-1（意味着要么在袋子里，要么不在）。然后我尝试将0-1（有界）背包代码变成多维的，但我无法添加卷限制以及0-1要求。如何编写0-1多维背包问题？或者如何调整代码以仅保持V的卷，所有项目卷都为1？代码不必是Java，但那是我目前拥有的语言。
背包问题：
package hu.pj.alg;
import hu.pj.obj.Item;
import java.util.*;
public class ZeroOneKnapsack {
protected List<Item> itemList = new ArrayList<Item>();
protected int maxWeight = 0;
protected int solutionWeight = 0;
protected int profit = 0;
protected boolean calculated = false;
public ZeroOneKnapsack() {}
public ZeroOneKnapsack(int _maxWeight) {
setMaxWeight(_maxWeight);
}
public ZeroOneKnapsack(List<Item> _itemList) {
setItemList(_itemList);
}
public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
// calculte the solution of 0-1 knapsack problem with dynamic method:
public List<Item> calcSolution() {
int n = itemList.size();
setInitialStateForCalculation();
if (n > 0 && maxWeight > 0) {
List< List<Integer> > c = new ArrayList< List<Integer> >();
List<Integer> curr = new ArrayList<Integer>();
c.add(curr);
for (int j = 0; j <= maxWeight; j++)
curr.add(0);
for (int i = 1; i <= n; i++) {
List<Integer> prev = curr;
c.add(curr = new ArrayList<Integer>());
for (int j = 0; j <= maxWeight; j++) {
if (j > 0) {
int wH = itemList.get(i-1).getWeight();
curr.add(
(wH > j)
?
prev.get(j)
:
Math.max(
prev.get(j),
itemList.get(i-1).getValue() + prev.get(j-wH)
)
);
} else {
curr.add(0);
}
} // for (j...)
} // for (i...)
profit = curr.get(maxWeight);
for (int i = n, j = maxWeight; i > 0 && j >= 0; i--) {
int tempI = c.get(i).get(j);
int tempI_1 = c.get(i-1).get(j);
if (
(i == 0 && tempI > 0)
||
(i > 0 && tempI != tempI_1)
)
{
Item iH = itemList.get(i-1);
int wH = iH.getWeight();
iH.setInKnapsack(1);
j -= wH;
solutionWeight += wH;
}
} // for()
calculated = true;
} // if()
return itemList;
}
// add an item to the item list
public void add(String name, int weight, int value) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value));
setInitialStateForCalculation();
}
// add an item to the item list
public void add(int weight, int value) {
add("", weight, value); // the name will be "itemList.size() + 1"!
}
// remove an item from the item list
public void remove(String name) {
for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) {
if (name.equals(it.next().getName())) {
it.remove();
}
}
setInitialStateForCalculation();
}
// remove all items from the item list
public void removeAllItems() {
itemList.clear();
setInitialStateForCalculation();
}
public int getProfit() {
if (!calculated)
calcSolution();
return profit;
}
public int getSolutionWeight() {return solutionWeight;}
public boolean isCalculated() {return calculated;}
public int getMaxWeight() {return maxWeight;}
public void setMaxWeight(int _maxWeight) {
maxWeight = Math.max(_maxWeight, 0);
}
public void setItemList(List<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
for (Item item : _itemList) {
item.checkMembers();
}
}
}
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(int inKnapsack) {
for (Item item : itemList)
if (inKnapsack > 0)
item.setInKnapsack(1);
else
item.setInKnapsack(0);
}
// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation() {
setInKnapsackByAll(0);
calculated = false;
profit = 0;
solutionWeight = 0;
}
} // class
同时，这个项目：
package hu.pj.obj;
public class Item {
protected String name = "";
protected int weight = 0;
protected int value = 0;
protected int bounding = 1; // the maximal limit of item's pieces
protected int inKnapsack = 0; // the pieces of item in solution
public Item() {}
public Item(Item item) {
setName(item.name);
setWeight(item.weight);
setValue(item.value);
setBounding(item.bounding);
}
public Item(int _weight, int _value) {
setWeight(_weight);
setValue(_value);
}
public Item(int _weight, int _value, int _bounding) {
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public Item(String _name, int _weight, int _value) {
setName(_name);
setWeight(_weight);
setValue(_value);
}
public Item(String _name, int _weight, int _value, int _bounding) {
setName(_name);
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public void setName(String _name) {name = _name;}
public void setWeight(int _weight) {weight = Math.max(_weight, 0);}
public void setValue(int _value) {value = Math.max(_value, 0);}
public void setInKnapsack(int _inKnapsack) {
inKnapsack = Math.min(getBounding(), Math.max(_inKnapsack, 0));
}
public void setBounding(int _bounding) {
bounding = Math.max(_bounding, 0);
if (bounding == 0)
inKnapsack = 0;
}
public void checkMembers() {
setWeight(weight);
setValue(value);
setBounding(bounding);
setInKnapsack(inKnapsack);
}
public String getName() {return name;}
public int getWeight() {return weight;}
public int getValue() {return value;}
public int getInKnapsack() {return inKnapsack;}
public int getBounding() {return bounding;}
} // class