Knapsack problem/Continuous
You are encouraged to solve this task according to the task description, using any language you may know.
See also: Knapsack problem and Wikipedia
A robber burgles in a butcher`s, wher he can select from some items. He knows the weights and prices of each items. Because he has a knapsack with 15 kg maximal capacity, he want to select from the items, that he would have the profit maximised. He may cut the items. Of course the item has a reduced price after cutting. The reduced item has proportional price with original price. That means: a half item has a half price of original.
This is the item list in the butcher`s:
| Item | Weight (kg) | Price (Value) |
|---|---|---|
| beef | 3.8 | 36 |
| pork | 5.4 | 43 |
| ham | 3.6 | 90 |
| greaves | 2.4 | 45 |
| flitch | 4.0 | 30 |
| brawn | 2.5 | 56 |
| welt | 3.7 | 67 |
| salami | 3.0 | 95 |
| sausage | 5.9 | 98 |
| Knapsack | <=15 kg | ? |
Which items does the robber carry in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximised?
Java
Greedy solution.
<lang java> package hu.pj.alg.test;
import hu.pj.alg.ContinuousKnapsack; import hu.pj.obj.Item; import java.util.*; import java.text.*;
public class ContinousKnapsackForRobber {
final private double tolerance = 0.0005;
public ContinousKnapsackForRobber() {
ContinuousKnapsack cok = new ContinuousKnapsack(15); // 15 kg
// making the list of items that you want to bring
cok.add("beef", 3.8, 36); // marhahús
cok.add("pork", 5.4, 43); // disznóhús
cok.add("ham", 3.6, 90); // sonka
cok.add("greaves", 2.4, 45); // tepertő
cok.add("flitch", 4.0, 30); // oldalas
cok.add("brawn", 2.5, 56); // disznósajt
cok.add("welt", 3.7, 67); // hurka
cok.add("salami", 3.0, 95); // szalámi
cok.add("sausage", 5.9, 98); // kolbász
// calculate the solution:
List<Item> itemList = cok.calcSolution();
// write out the solution in the standard output
if (cok.isCalculated()) {
NumberFormat nf = NumberFormat.getInstance();
System.out.println(
"Maximal weight = " +
nf.format(cok.getMaxWeight()) + " kg"
);
System.out.println(
"Total weight of solution = " +
nf.format(cok.getSolutionWeight()) + " kg"
);
System.out.println(
"Total value (profit) = " +
nf.format(cok.getProfit())
);
System.out.println();
System.out.println(
"You can carry te following materials " +
"in the knapsack:"
);
for (Item item : itemList) {
if (item.getInKnapsack() > tolerance) {
System.out.format(
"%1$-10s %2$-15s %3$-15s \n",
nf.format(item.getInKnapsack()) + " kg ",
item.getName(),
"(value = " + nf.format(item.getInKnapsack() * (item.getValue() / item.getWeight())) + ")"
);
}
}
} else {
System.out.println(
"The problem is not solved. " +
"Maybe you gave wrong data."
);
}
}
public static void main(String[] args) {
new ContinousKnapsackForRobber();
}
} // class</lang>
<lang java> package hu.pj.alg;
import hu.pj.obj.Item; import java.util.*;
public class ContinuousKnapsack {
protected List<Item> itemList = new ArrayList<Item>(); protected double maxWeight = 0; protected double solutionWeight = 0; protected double profit = 0; protected boolean calculated = false;
public ContinuousKnapsack() {}
public ContinuousKnapsack(double _maxWeight) {
setMaxWeight(_maxWeight);
}
public List<Item> calcSolution() {
int n = itemList.size();
setInitialStateForCalculation();
if (n > 0 && maxWeight > 0) {
Collections.sort(itemList);
for (int i = 0; (maxWeight - solutionWeight) > 0.0 && i < n; i++) {
Item item = itemList.get(i);
if (item.getWeight() >= (maxWeight - solutionWeight)) {
item.setInKnapsack(maxWeight - solutionWeight);
solutionWeight = maxWeight;
profit += item.getInKnapsack() / item.getWeight() * item.getValue();
break;
} else {
item.setInKnapsack(item.getWeight());
solutionWeight += item.getInKnapsack();
profit += item.getValue();
}
}
calculated = true;
}
return itemList;
}
// add an item to the item list
public void add(String name, double weight, double value) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value));
setInitialStateForCalculation();
}
public double getMaxWeight() {return maxWeight;}
public double getProfit() {return profit;}
public double getSolutionWeight() {return solutionWeight;}
public boolean isCalculated() {return calculated;}
public void setMaxWeight(double _maxWeight) {
maxWeight = Math.max(_maxWeight, 0);
}
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(double 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(-0.0001);
calculated = false;
profit = 0.0;
solutionWeight = 0.0;
}
} // class</lang>
<lang java> package hu.pj.obj;
public class Item implements Comparable {
protected String name = ""; protected double weight = 0; protected double value = 0; protected double inKnapsack = 0; // the weight of item in solution
public Item() {}
public Item(Item item) {
setName(item.name);
setWeight(item.weight);
setValue(item.value);
}
public Item(double _weight, double _value) {
setWeight(_weight);
setValue(_value);
}
public Item(String _name, double _weight, double _value) {
setName(_name);
setWeight(_weight);
setValue(_value);
}
public void setName(String _name) {name = _name;}
public void setWeight(double _weight) {weight = Math.max(_weight, 0);}
public void setValue(double _value) {value = Math.max(_value, 0);}
public void setInKnapsack(double _inKnapsack) {
inKnapsack = Math.max(_inKnapsack, 0);
}
public void checkMembers() {
setWeight(weight);
setValue(value);
setInKnapsack(inKnapsack);
}
public String getName() {return name;}
public double getWeight() {return weight;}
public double getValue() {return value;}
public double getInKnapsack() {return inKnapsack;}
// implementing of Comparable interface:
public int compareTo(Object item) {
int result = 0;
Item i2 = (Item)item;
double rate1 = value / weight;
double rate2 = i2.value / i2.weight;
if (rate1 > rate2) result = -1; // if greater, put it previously
else if (rate1 < rate2) result = 1;
return result;
}
} // class</lang>
output:
Maximal weight = 15 kg Total weight of solution = 15 kg Total value (profit) = 349,378 You can carry te following materials in the knapsack: 3 kg salami (value = 95) 3,6 kg ham (value = 90) 2,5 kg brawn (value = 56) 2,4 kg greaves (value = 45) 3,5 kg welt (value = 63,378)