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 a butcher's shop, where 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 wants to select the items such that he would have his profit maximized. He may cut the items; the item has a reduced price after cutting that is proportional to the original price by the ratio of masses. That means: half of an item has half the price of the 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?
Haskell
We use a greedy algorithm.
<lang haskell>import Control.Monad import Data.List (sortBy) import Data.Ord (comparing) import Data.Ratio (numerator, denominator) import Text.Printf
maxWgt = 15
data Bounty = Bounty
{itemName :: String,
itemVal, itemWgt :: Rational}
items =
[Bounty "beef" 36 3.8, Bounty "pork" 43 5.4, Bounty "ham" 90 3.6, Bounty "greaves" 45 2.4, Bounty "flitch" 30 4.0, Bounty "brawn" 56 2.5, Bounty "welt" 67 3.7, Bounty "salami" 95 3.0, Bounty "sausage" 98 5.9]
solution :: [(Rational, Bounty)] solution = g maxWgt $ sortBy (flip $ comparing f) items
where g room (b@(Bounty _ _ w) : bs) = if w < room
then (w, b) : g (room - w) bs
else [(room, b)]
f (Bounty _ v w) = v / w
main = do
forM_ solution $ \(w, b) ->
printf "%s kg of %s\n" (mixedNum w) (itemName b)
printf "Total value: %s\n" $ mixedNum $ sum $ map f solution
where f (w, Bounty _ v wtot) = v * (w / wtot)
mixedNum q = if b == 0
then show a
else printf "%d %d/%d" a (numerator b) (denominator b)
where a = floor q
b = q - toEnum a</lang>
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 the 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 the 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)
OCaml
<lang ocaml>let items =
[ "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; ]
let () =
let items = List.map (fun (name, w, p) -> (name, w, p, float p /. w)) items in
let items = List.sort (fun (_,_,_,v1) (_,_,_,v2) -> compare v2 v1) items in
let rec loop acc weight = function
| ((_,w,_,_) as item) :: tl ->
if w +. weight > 15.0
then (weight, acc, item)
else loop (item::acc) (w +. weight) tl
| [] -> assert false
in
let weight, res, (last,w,p,v) = loop [] 0.0 items in
print_endline " Items Weight Price";
let price =
List.fold_left (fun price (name,w,p,_) ->
Printf.printf " %7s: %6.2f %3d\n" name w p;
(p + price)
) 0 res
in
let rem_weight = 15.0 -. weight in
let last_price = v *. rem_weight in
Printf.printf " %7s: %6.2f %6.2f\n" last rem_weight last_price;
Printf.printf " Total Price: %.3f\n" (float price +. last_price);
- </lang>
Python
I think this greedy algorithm of taking the largest amounts of items ordered by their value per unit weight is maximal: <lang python>items = [ # NAME, WEIGHT, VALUE (for this weight)
('beef', 3.8, 36.0),
('pork', 5.4, 43.0),
('ham', 3.6, 90.0),
('greaves', 2.4, 45.0),
('flitch', 4.0, 30.0),
('brawn', 2.5, 56.0),
('welt', 3.7, 67.0),
('salami', 3.0, 95.0),
('sausage', 5.9, 98.0)]
maxwt = 15.0
sorteditems = sorted( ((value/amount, amount, name)
for name, amount, value in items),
reverse = True)
wt = val = 0 bagged = [] for unitvalue, amount, name in sorteditems:
portion = min(maxwt - wt, amount)
wt += portion
addval = portion * unitvalue
val += addval
bagged += [(name, portion, addval)]
if wt >= maxwt:
break
print(" ITEM PORTION VALUE") print('\n'.join("%10s %6.2f %6.2f" % item for item in bagged))
print("\nTOTAL WEIGHT: %5.2f\nTOTAL VALUE: %5.2f" % (wt, val))</lang>
Sample Output
ITEM PORTION VALUE
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
TOTAL WEIGHT: 15.00
TOTAL VALUE: 349.38
Tcl
<lang tcl>package require Tcl 8.5
- Uses the trivial greedy algorithm
proc continuousKnapsack {items massLimit} {
# Add in the unit prices
set idx -1
foreach item $items {
lassign $item name mass value lappend item [expr {$value / $mass}] lset items [incr idx] $item
}
# Sort by unit prices set items [lsort -decreasing -real -index 3 $items]
# Add items, using most valuable-per-unit first
set result {}
set total 0.0
set totalValue 0
foreach item $items {
lassign $item name mass value unit if {$total + $mass < $massLimit} { lappend result [list $name $mass $value] set total [expr {$total + $mass}] set totalValue [expr {$totalValue + $value}] } else { set mass [expr {$massLimit - $total}] set value [expr {$unit * $mass}] lappend result [list $name $mass $value] set totalValue [expr {$totalValue + $value}] break }
}
# We return the total value too, purely for convenience return [list $result $totalValue]
}</lang> Driver for this particular problem: <lang tcl>set items {
{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}
}
lassign [continuousKnapsack $items 15.0] contents totalValue puts [format "total value of knapsack: %.2f" $totalValue] puts "contents:" foreach item $contents {
lassign $item name mass value puts [format "\t%.1fkg of %s, value %.2f" $mass $name $value]
}</lang> Output:
total value of knapsack: 349.38 contents: 3.0kg of salami, value 95.00 3.6kg of ham, value 90.00 2.5kg of brawn, value 56.00 2.4kg of greaves, value 45.00 3.5kg of welt, value 63.38
Ursala
We might as well leave this one to the experts by setting it up as a linear programming problem and handing it off to an external library (which will be either lpsolve or glpk depending on the run-time system configuration). <lang Ursala>#import flo
- import lin
items = # name: (weight,price)
<
'beef ': (3.8,36.0), 'pork ': (5.4,43.0), 'ham ': (3.6,90.0), 'greaves': (2.4,45.0), 'flitch ': (4.0,30.0), 'brawn ': (2.5,56.0), 'welt ': (3.7,67.0), 'salami ': (3.0,95.0), 'sausage': (5.9,98.0)>
system = # a function to transform the item list to the data structure needed by the solver
linear_system$[
lower_bounds: *nS ~&\0., # all zeros because we can't steal less than zero upper_bounds: ~&nmlPXS, # can't steal more than what's in the shop costs: * ^|/~& negative+ vid, # prices divided by weights, negated so as to maximize equations: ~&iNC\15.+ 1.-*@nS] # 1 equation constraining the total weight to 15
- cast %em
main = solution system items</lang> output:
< 'brawn ': 2.500000e+00, 'greaves': 2.400000e+00, 'ham ': 3.600000e+00, 'salami ': 3.000000e+00, 'welt ': 3.500000e+00>