Knapsack problem/Continuous
See also: Knapsack problem and Wikipedia
You are encouraged to solve this task according to the task description, using any language you may know.
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)