Knapsack problem/0-1
You are encouraged to solve this task according to the task description, using any language you may know.
See also: Knapsack problem
A turist wants to make a good trip at the weekend with his friends. They will go to the mountains to wonder the nature. So he needs some items during the trip. Food, cloths, other... He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening. He creates a list what he wants to bring for the trip, but the total weight of all items is too much. He adds a value to each item. The value represets how important the thing for the turist.
This is the list:
| Item | Weight (dkg) | Value |
| map | 9 | 150 |
| compass | 13 | 35 |
| water | 153 | 200 |
| sandwich | 50 | 160 |
| glucose | 15 | 60 |
| tin | 68 | 45 |
| banana | 27 | 60 |
| apple | 39 | 40 |
| cheese | 23 | 30 |
| beer | 52 | 10 |
| suntan cream | 11 | 70 |
| camera | 32 | 30 |
| t-shirt | 24 | 15 |
| trousers | 48 | 10 |
| umbrella | 73 | 40 |
| waterproof trousers | 42 | 70 |
| waterproof overcloths | 43 | 75 |
| note-case | 22 | 80 |
| sunglasses | 7 | 20 |
| towel | 18 | 12 |
| socks | 4 | 50 |
| book | 30 | 10 |
| Knapsack | <=400 dkg | ? |
He can only take whole units of any item, and he has only one piece from the items.
Which items he has to carry in his knapsack that the weight of knapsack does not have to exceed the 4 kg maximal weight, and the total value has to be maximal?
Java
General dinamic solution after wikipedia.
<lang java> package hu.pj.alg.test;
import hu.pj.alg.ZeroOneKnapsack; import hu.pj.obj.Item; import java.util.*; import java.text.*;
public class ZeroOneKnapsackForTurists {
public ZeroOneKnapsackForTurists() {
Vector<Item> itemList;
ZeroOneKnapsack zok = new ZeroOneKnapsack(400); // 400 dkg = 4kg
// making the list of items that you want to bring
zok.add("map", 9, 150);
zok.add("compass", 13, 35);
zok.add("water", 153, 200);
zok.add("sandwich", 50, 160);
zok.add("glucose", 15, 60);
zok.add("tin", 68, 45);
zok.add("banana", 27, 60);
zok.add("apple", 39, 40);
zok.add("cheese", 23, 30);
zok.add("beer", 52, 10);
zok.add("suntan cream", 11, 70);
zok.add("camera", 32, 30);
zok.add("t-shirt", 24, 15);
zok.add("trousers", 48, 10);
zok.add("umbrella", 73, 40);
zok.add("waterproof trousers", 42, 70);
zok.add("waterproof overclothes", 43, 75);
zok.add("note-case", 22, 80);
zok.add("sunglasses", 7, 20);
zok.add("towel", 18, 12);
zok.add("socks", 4, 50);
zok.add("book", 30, 10);
// calculate the solution:
itemList = zok.calcSolution();
// write out the solution in the standard output
if (zok.isCalculated()) {
NumberFormat nf = NumberFormat.getInstance();
System.out.println(
"Maximal weight = " +
nf.format(zok.getMaxWeight() / 100.0) + " kg"
);
System.out.println(
"Total weight of solution = " +
nf.format(zok.getSolutionWeight() / 100.0) + " kg"
);
System.out.println(
"Total value = " +
zok.getProfit()
);
System.out.println();
System.out.println(
"You can carry te following materials " +
"in the knapsack:"
);
for (Item item : itemList) {
if (item.isInKnapsack()) {
System.out.format(
"%1$-23s %2$-3s %3$-5s %4$-15s \n",
item.getName(),
item.getWeight(), "dkg ",
"(value = " + item.getValue() + ")"
);
}
}
} else {
System.out.println(
"The problem is not solved. " +
"Maybe you gave wrong data."
);
}
}
public static void main(String[] args) {
new ZeroOneKnapsackForTurists();
}
} </lang>
<lang java> package hu.pj.alg;
import hu.pj.obj.Item; import java.util.*;
public class ZeroOneKnapsack {
private Vector<Item> itemList = new Vector<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(Vector<Item> _itemList) {
setItemList(_itemList);
}
public ZeroOneKnapsack(Vector<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
// calculte the solution of 0-1 knapsack problem with dinamic method:
public Vector<Item> calcSolution() {
int n = itemList.size();
setInitialStateForCalculation();
if (n > 0 && maxWeight > 0) {
int i, j;
Vector< Vector<Integer> > c = new Vector< Vector<Integer> >();
Vector<Integer> curr = new Vector<Integer>();
c.add(curr);
for (j = 0; j <= maxWeight; j++)
curr.add(0);
for (i = 1; i <= n; i++) {
Vector<Integer> prev = curr;
c.add(curr = new Vector<Integer>());
for (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);
i = n;
j = maxWeight;
while ((i > 0) && (j >= 0)) {
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(true);
j -= wH;
solutionWeight += wH;
}
i--;
} // while()
calculated = true;
} // if()
return itemList;
}
// add an item to the item list
public void add(String name, int weight, int value) {
if (name.compareTo("") == 0)
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) {
if (itemList.size() > 0) {
int n = itemList.size();
for (int i = 0; i < n; i++) {
if (name.compareTo(itemList.get(i).getName()) == 0) {
itemList.remove(i);
n--;
i--;
}
}
}
setInitialStateForCalculation();
}
// remove all items from the item list
public void removeAllItems() {
itemList.removeAllElements();
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(Vector<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
setInKnapsackByAll(false);
}
}
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(boolean inKnapsack) {
for (Item item : itemList)
item.setInKnapsack(inKnapsack);
}
// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation() {
setInKnapsackByAll(false);
calculated = false;
profit = 0;
solutionWeight = 0;
}
} // class </lang>
<lang java> package hu.pj.obj;
public class Item extends Object {
protected String name = ""; protected int weight = 0; protected int value = 0; protected boolean inKnapsack = false;
public Item() {}
public Item(Item item) {
setName(item.name);
setWeight(item.weight);
setValue(item.value);
}
public Item(int _weight, int _value) {
setWeight(_weight);
setValue(_value);
}
public Item(String _name, int _weight, int _value) {
setName(_name);
setWeight(_weight);
setValue(_value);
}
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(boolean inKnaps) {inKnapsack = inKnaps;}
public String getName() {return name;}
public int getWeight() {return weight;}
public int getValue() {return value;}
public boolean isInKnapsack() {return inKnapsack;}
} // class </lang>
output:
Maximal weight = 4 kg Total weight of solution = 3,96 kg Total value = 1030 You can carry te following materials in the knapsack: map 9 dkg (value = 150) compass 13 dkg (value = 35) water 153 dkg (value = 200) sandwich 50 dkg (value = 160) glucose 15 dkg (value = 60) banana 27 dkg (value = 60) suntan cream 11 dkg (value = 70) waterproof trousers 42 dkg (value = 70) waterproof overclothes 43 dkg (value = 75) note-case 22 dkg (value = 80) sunglasses 7 dkg (value = 20) socks 4 dkg (value = 50)