0-1 Multidimensional Backpack

Question

So, I am trying to create an algorithm that will find the best combination of n elements (in my case 4) that can only be placed in a backpack once (0-1) with a maximum weight capacity. To summarize, probably more efficiently, I want to place no more than four unique items in my backpack so that their weight is less than a certain value of W, and their maximum total value. My first attempt and assumption was to set the volume limit to 4, while all volumes of objects are 1 for the multidimensional knapsack problem. But I ran into the problem that this is not 0-1 (which means either in the bag or not). Then I tried to make the 0-1 (limited) knapsack code multidimensional, but I was not able to add a volume limit, as well as a 0-1 requirement. How can I ask a 0-1 multidimensional backpack problem? Or how can I adapt the code to only store volume V when all item volumes are 1? The code should not be Java, but this is what I have so far.

Backpack:

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 

And the item:

 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 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 

Answer 1

Here is a general implementation to solve the 0-1 backpack problem with two sizes (size and volume). I used a matrix instead of a list because it is much simpler. That's the whole class, as well as the main method of testing it.
To add dimensions, simply add new dimensions to the matrix and add inner loops to check all conditions.

 public class MultidimensionalKnapsack { /** The size of the knapsack */ private static int size; /** The volume of the knapsack */ private static int vol; private static class Item { public int value; public int size; public int volume; public Item(int v, int w, int vol) { value = v; size = w; volume = vol; } } // Knapsack 0/1 without repetition // Row: problem having only the first i items // Col: problem having a knapsack of size j // Third dimension: problem having a knapsack of volume h private static int[][][] dynNoRep; private static void noRep(Item[] items) { dynNoRep = new int[items.length + 1][size + 1][vol + 1]; for(int j = 0; j <= size; j++) { dynNoRep[0][j][0] = 0; } for(int i = 0; i <= vol; i++) { dynNoRep[0][0][i] = 0; } for(int i = 0; i <= items.length; i++) { dynNoRep[i][0][0] = 0; } for(int i = 1; i <= items.length; i++) for(int j = 0; j <= size; j++) { for(int h = 0; h <= vol; h++) { if(items[i - 1].size > j) // If the item i is too big, I can't put it and the solution is the same of the problem with i - 1 items dynNoRep[i][j][h] = dynNoRep[i - 1][j][h]; else { if(items[i - 1].volume > h) // If the item i is too voluminous, I can't put it and the solution is the same of the problem with i - 1 items dynNoRep[i][j][h] = dynNoRep[i - 1][j][h]; else { // The item i could be useless and the solution is the same of the problem with i - 1 items, or it could be // useful and the solution is "(solution of knapsack of size j - item[i].size and volume h - item[i].volume) + item[i].value" dynNoRep[i][j][h] = Math.max(dynNoRep[i - 1][j][h], dynNoRep[i - 1][j - items[i - 1].size][h - items[i - 1].volume] + items[i - 1].value); } } } } } public static void main(String[] args) { size = 15; vol = 12; Item[] items = {new Item(2, 4, 1), new Item(1, 5, 4), new Item(6, 3, 9), new Item(3, 3, 19), new Item(7, 2, 7), new Item(1, 2, 6), new Item(2, 1, 2), new Item(10, 9, 12), new Item(9, 10, 2), new Item(24, 23, 11)}; System.out.print("We have the following " + items.length + " items (value, size, volume): "); for(int i = 0; i < items.length; i++) System.out.print("(" + items[i].value + ", " + items[i].size + ", " + items[i].volume + ") "); System.out.println(); System.out.println("And a knapsack of size " + size + " and volume " + vol); noRep(items); System.out.println(); // Print the solution int j = size, h = vol, finalSize = 0, finalValue = 0, finalVolume = 0; System.out.print("Items picked (value, size, volume) for 0/1 problems without repetitions: "); for(int i = items.length; i > 0; i--) { if(dynNoRep[i][j][h] != dynNoRep[i - 1][j][h]) { System.out.print("(" + items[i - 1].value + ", " + items[i - 1].size + ", " + items[i - 1].volume + ") "); finalSize += items[i - 1].size; finalValue += items[i - 1].value; finalVolume += items[i - 1].volume; j -= items[i - 1].size; h -= items[i - 1].volume; } } System.out.println(); System.out.println(" Final size: " + finalSize); System.out.println(" Final volume: " + finalVolume); System.out.println(" Final value: " + finalValue); } 

}