# Knapsack problem/Continuous

Knapsack problem/Continuous
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:

Table of potential knapsack items
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?

procedure Knapsack_Continuous is

```  package US renames Ada.Strings.Unbounded;
```
```  type Item is record
Name   : US.Unbounded_String;
Weight : Float;
Value  : Positive;
Taken  : Float;
end record;
```
```  function "<" (Left, Right : Item) return Boolean is
begin
return Float (Left.Value) / Left.Weight <
Float (Right.Value) / Right.Weight;
end "<";
```
```  type Item_Array is array (Positive range <>) of Item;
```
```  function Total_Weight (Items : Item_Array) return Float is
Sum : Float := 0.0;
begin
for I in Items'Range loop
Sum := Sum + Items (I).Weight * Items (I).Taken;
end loop;
return Sum;
end Total_Weight;
```
```  function Total_Value (Items : Item_Array) return Float is
Sum : Float := 0.0;
begin
for I in Items'Range loop
Sum := Sum + Float (Items (I).Value) * Items (I).Taken;
end loop;
return Sum;
end Total_Value;
```
```  procedure Solve_Knapsack_Continuous
(Items        : in out Item_Array;
Weight_Limit : Float)
is
begin
-- order items by value per weight unit
Sorting : declare
An_Item : Item;
J       : Natural;
begin
for I in Items'First + 1 .. Items'Last loop
An_Item := Items (I);
J       := I - 1;
while J in Items'Range and then Items (J) < An_Item loop
Items (J + 1) := Items (J);
J             := J - 1;
end loop;
Items (J + 1) := An_Item;
end loop;
end Sorting;
declare
Rest : Float := Weight_Limit;
begin
for I in Items'Range loop
if Items (I).Weight <= Rest then
Items (I).Taken := Items (I).Weight;
else
Items (I).Taken := Rest;
end if;
Rest := Rest - Items (I).Taken;
exit when Rest <= 0.0;
end loop;
end;
end Solve_Knapsack_Continuous;
```
```  All_Items : Item_Array :=
((US.To_Unbounded_String ("beef"), 3.8, 36, 0.0),
(US.To_Unbounded_String ("pork"), 5.4, 43, 0.0),
(US.To_Unbounded_String ("ham"), 3.6, 90, 0.0),
(US.To_Unbounded_String ("greaves"), 2.4, 45, 0.0),
(US.To_Unbounded_String ("flitch"), 4.0, 30, 0.0),
(US.To_Unbounded_String ("brawn"), 2.5, 56, 0.0),
(US.To_Unbounded_String ("welt"), 3.7, 67, 0.0),
(US.To_Unbounded_String ("salami"), 3.0, 95, 0.0),
(US.To_Unbounded_String ("sausage"), 5.9, 98, 0.0));
```

begin

```  Solve_Knapsack_Continuous (All_Items, 15.0);
("Total Weight: " & Float'Image (Total_Weight (All_Items)));
("Total Value:  " & Float'Image (Total_Value (All_Items)));
for I in All_Items'Range loop
if All_Items (I).Taken > 0.0 then
("   " &
Float'Image (All_Items (I).Taken) &
" of " &
US.To_String (All_Items (I).Name));
end if;
end loop;
```

end Knapsack_Continuous;</lang>

## C

<lang c>#include <stdio.h>

1. include <stdlib.h>

struct item { double w, v; char *name; } items[] = { { 3.8, 36, "beef" }, { 5.4, 43, "pork" }, { 3.6, 90, "ham" }, { 2.4, 45, "greaves" }, { 4.0, 30, "flitch" }, { 2.5, 56, "brawn" }, { 3.7, 67, "welt" }, { 3.0, 95, "salami" }, { 5.9, 98, "sausage" }, };

int item_cmp(const void *aa, const void *bb) { const struct item *a = aa, *b = bb; double ua = a->v / a->w, ub = b->v / b->w; return ua < ub ? -1 : ua > ub; }

int main() { struct item *it; double space = 15;

qsort(items, 9, sizeof(struct item), item_cmp); for (it = items + 9; it---items && space > 0; space -= it->w) if (space >= it->w) printf("take all %s\n", it->name); else printf("take %gkg of %g kg of %s\n", space, it->w, it->name);

return 0;

}</lang>output

```take all salami
take all ham
take all brawn
take all greaves
take 3.5kg of 3.7 kg of welt
```

## C++

<lang cpp>

1. include<iostream>
2. include<algorithm>
3. include<string.h>

using namespace std; double result; double capacity = 15; int NumberOfItems; int number;

struct items {

```   char name[32];
double weight;
double price;
double m;
```

} item[256];

bool cmp(items a,items b) {

```   return a.price/a.weight > b.price/b.weight; // the compare function for the sorting algorithm
```

}

int main() { NumberOfItems=9; strcpy(item[1].name,"beef"); item[1].weight=3.8; item[1].price=36;

strcpy(item[2].name,"pork"); item[2].weight=5.4; item[2].price=43;

strcpy(item[3].name,"ham"); item[3].weight=3.6; item[3].price=90;

strcpy(item[4].name,"greaves"); item[4].weight=2.4; item[4].price=45;

strcpy(item[5].name,"flitch"); item[5].weight=4.0; item[5].price=30;

strcpy(item[6].name,"brawn"); item[6].weight=2.5; item[6].price=56;

strcpy(item[7].name,"welt"); item[7].weight=3.7; item[7].price=67;

strcpy(item[8].name,"salami"); item[8].weight=3.0; item[8].price=95;

strcpy(item[9].name,"sausage"); item[9].weight=5.9; item[9].price=98;

sort(item+1,item+NumberOfItems+1,cmp); // We'll sort using Introsort from STL

```number = 1;
while(capacity>0&&number<=NumberOfItems)
{
if(item[number].weight<=capacity)
{
result+=item[number].price;
capacity-=item[number].weight;
item[number].m=1;
}
else
{
result+=(item[number].price)*(capacity/item[number].weight);
item[number].m=(capacity/item[number].weight);
capacity=0;
```
``` }
++number;
}
```

cout<<"Total Value = "<<result<<'\n'; cout<<"Total Weight = "<<(double)15-capacity<<'\n'; cout<<"Items Used:\n"; for(int i=1;i<=NumberOfItems;++i)

```   if(item[i].m)
{
cout<<"We took "<<item[i].m*item[i].weight<<"kg of \""<<item[i].name<<"\" and the value it brought is "<<item[i].price*item[i].m<<"\n";
}
```

return 0; }

</lang>

## D

<lang d>import std.stdio, std.algorithm, std.string, std.conv;

struct Item {

```   string name;
real amount, value;
```
```   @property real valuePerKG() const pure nothrow {
return value / amount;
}
```
```   string toString() const /*pure nothrow*/ {
return format("%10s %7.2f %7.2f %7.2f",
name, amount, value, valuePerKG);
}
```

}

real sum(string field)(in Item[] items) pure nothrow {

```   //return reduce!("a + b." ~ field)(0.0L, items);
return reduce!("a + b." ~ field)(0.0L, cast()items);
```

}

void main() {

```   Item[] raw = [{"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}];
```
```   // reverse sorted by Value per amount
const items = raw.sort!q{a.valuePerKG > b.valuePerKG}().release();
```
```   const(Item)[] chosen;
real space = 15.0;
foreach (item; items)
if (item.amount < space) {
chosen ~= item;
space -= item.amount;
} else {
chosen ~= Item(item.name, space,
item.valuePerKG * space);
break;
}
```
```   writefln("%10s %7s %7s %7s", "ITEM", "AMOUNT", "VALUE", "\$/unit");
chosen.map!text().join("\n").writeln();
writeln(Item("TOTAL", sum!"amount"(chosen), sum!"value"(chosen)));
```

}</lang> output:

```      ITEM  AMOUNT   VALUE  \$/unit
salami    3.00   95.00   31.67
ham    3.60   90.00   25.00
brawn    2.50   56.00   22.40
greaves    2.40   45.00   18.75
welt    3.50   63.38   18.11
TOTAL   15.00  349.38   23.29```

## Fortran

Works with: Fortran version 90 and later

<lang fortran>program KNAPSACK_CONTINUOUS

``` implicit none

real, parameter :: maxweight = 15.0
real :: total_weight = 0, total_value = 0, frac
integer :: i, j

type Item
character(7) :: name
real :: weight
real :: value
end type Item
```
``` type(Item) :: items(9), temp

items(1) = Item("beef",    3.8, 36.0)
items(2) = Item("pork",    5.4, 43.0)
items(3) = Item("ham",     3.6, 90.0)
items(4) = Item("greaves", 2.4, 45.0)
items(5) = Item("flitch",  4.0, 30.0)
items(6) = Item("brawn",   2.5, 56.0)
items(7) = Item("welt",    3.7, 67.0)
items(8) = Item("salami",  3.0, 95.0)
items(9) = Item("sausage", 5.9, 98.0)
```
``` ! sort items in desending order of their value per unit weight
do i = 2, size(items)
j = i - 1
temp = items(i)
do while (j>=1 .and. items(j)%value / items(j)%weight < temp%value / temp%weight)
items(j+1) = items(j)
j = j - 1
end do
items(j+1) = temp
end do

i = 0
write(*, "(a4, a13, a6)") "Item", "Weight", "Value"
do while(i < size(items) .and. total_weight < maxweight)
i = i + 1
if(total_weight+items(i)%weight < maxweight) then
total_weight = total_weight + items(i)%weight
total_value = total_value + items(i)%value
write(*, "(a7, 2f8.2)") items(i)
else
frac = (maxweight-total_weight) / items(i)%weight
total_weight = total_weight + items(i)%weight * frac
total_value = total_value + items(i)%value * frac
write(*, "(a7, 2f8.2)") items(i)%name, items(i)%weight * frac, items(i)%value * frac
end if
end do
```
``` write(*, "(f15.2, f8.2)") total_weight, total_value

```

end program KNAPSACK_CONTINUOUS</lang>

## Go

<lang go>package main

import (

```   "fmt"
"sort"
```

)

type item struct {

```   item   string
weight float64
price  float64
```

}

type items []item

var all = 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},
```

}

// satisfy sort interface func (z items) Len() int { return len(z) } func (z items) Swap(i, j int) { z[i], z[j] = z[j], z[i] } func (z items) Less(i, j int) bool {

```   return z[i].price/z[i].weight > z[j].price/z[j].weight
```

}

func main() {

```   left := 15.
sort.Sort(all)
for _, i := range all {
if i.weight <= left {
fmt.Println("take all the", i.item)
if i.weight == left {
return
}
left -= i.weight
} else {
fmt.Printf("take %.1fkg %s\n", left, i.item)
return
}
}
```

}</lang> Output:

```take all the salami
take all the ham
take all the brawn
take all the greaves
take 3.5kg welt
```

## Groovy

Solution: obvious greedy algorithm <lang groovy>import static java.math.RoundingMode.*

def knapsackCont = { list, maxWeight = 15.0 ->

```   list.sort{ it.weight / it.value }
def remainder = maxWeight
List sack = []
for (item in list) {
if (item.weight < remainder) {
sack << [name: item.name, weight: item.weight,
value: (item.value as BigDecimal).setScale(2, HALF_UP)]
} else {
sack << [name: item.name, weight: remainder,
value: (item.value * remainder / item.weight).setScale(2, HALF_UP)]
break
}
remainder -= item.weight
}
sack
```

}</lang>

Test: <lang groovy>def possibleItems = [

```   [name:'beef',    weight:3.8, value:36],
[name:'pork',    weight:5.4, value:43],
[name:'ham',     weight:3.6, value:90],
[name:'greaves', weight:2.4, value:45],
[name:'flitch',  weight:4.0, value:30],
[name:'brawn',   weight:2.5, value:56],
[name:'welt',    weight:3.7, value:67],
[name:'salami',  weight:3.0, value:95],
[name:'sausage', weight:5.9, value:98],
```

]

def contents = knapsackCont(possibleItems) println "Total Value: \${contents*.value.sum()}" contents.each {

```   printf("    name: %-7s  weight: \${it.weight}  value: \${it.value}\n", it.name)
```

}</lang>

Output:

```Total Value: 349.38
name: salami   weight: 3.0  value: 95.00
name: ham      weight: 3.6  value: 90.00
name: brawn    weight: 2.5  value: 56.00
name: greaves  weight: 2.4  value: 45.00
name: welt     weight: 3.5  value: 63.38```

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

Or similar to above (but more succinct): <lang haskell> import Data.List (sortBy) import Data.Ord (comparing) import Text.Printf (printf)

-- (name, (value, weight)) items = [("beef", (36, 3.8)),

```        ("pork",    (43, 5.4)),
("ham",     (90, 3.6)),
("greaves", (45, 2.4)),
("flitch",  (30, 4.0)),
("brawn",   (56, 2.5)),
("welt",    (67, 3.7)),
("salami",  (95, 3.0)),
("sausage", (98, 5.9))]
```

unitWeight (_, (val, weight)) = (fromIntegral val) / weight

solution k = loop k . sortBy (flip \$ comparing unitWeight)

```   where loop k ((name, (_, weight)):xs)
| weight < k = ["Take all the " ++ name] ++ loop (k-weight) xs
| otherwise  = [printf "Take %.2f kg of the %s" (k :: Float) name]
```

main = mapM_ putStrLn \$ solution 15 items </lang>

## Icon and Unicon

This implements the greedy algorithm. This also uses a Unicon extension to reverse which reverses a list. In Icon, an IPL procedure is available to do the same. <lang Icon>link printf

procedure main() room := 15 every (x := !(choices := get_items())).uprice := x.price / x.weight choices := reverse(sortf(choices,4))

every (value := 0, x := !choices) do {

```  if x.weight <= room then {
printf("Take all of the %s (%r kg) worth \$%r\n",x.name,x.weight,x.price)
value +:= x.price
room -:= x.weight
}
else {
fvalue := x.uprice * room
printf("Take (%r kg) of the %s worth \$%r\n",room,x.name,fvalue)
value +:= fvalue
break
}
```

} printf("Total value of a full knapsack is \$%r\n",value) end

record item(name,weight,price,uprice)

procedure get_items()

```  return [  item("beef", 3.8, 36),
item("pork", 5.4, 43),
item("ham", 3.6, 90),
item("greaves", 2.4, 45),
item("flitch", 4.0, 30),
item("brawn", 2.5, 56),
item("welt", 3.7, 67),
item("salami", 3.0, 95),
item("sausage", 5.9, 98) ]
```

end</lang>

Output:

```Take all of the salami (3.000000 kg) worth \$95.000000
Take all of the ham (3.600000 kg) worth \$90.000000
Take all of the brawn (2.500000 kg) worth \$56.000000
Take all of the greaves (2.400000 kg) worth \$45.000000
Take (3.500000 kg) of the welt worth \$63.378378
Total value of a full knapsack is \$349.378378```

## J

We take as much as we can of the most valuable items first, and continue until we run out of space. Only one item needs to be cut.

<lang J>'names numbers'=:|:;:;._2]0 :0 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 ) 'weights prices'=:|:".numbers order=: \:prices%weights take=: 15&<.&.(+/\) order{weights result=: (*take)#(order{names),.' ',.":,.take</lang>

This gives the result:

```salami    3
ham     3.6
brawn   2.5
greaves 2.4
welt    3.5
```

For a total value of: <lang J> +/prices * (take/:order) % weights 349.378</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
```
```       // 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);
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)```

## Mathprog

<lang>/*Knapsack

``` This model finds the optimal packing of a knapsack

Nigel_Galloway
January 10th., 2012
```
• /

set Items; param weight{t in Items}; param value{t in Items};

var take{t in Items}, >=0, <=weight[t];

knap_weight : sum{t in Items} take[t] <= 15;

maximize knap_value: sum{t in Items} take[t] * (value[t]/weight[t]);

data;

param : Items  : weight 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
;
```

end;</lang>

The solution is here at Knapsack problem/Continuous/Mathprog.

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

## Perl

<lang perl>my @items = sort { \$b->[2]/\$b->[1] <=> \$a->[2]/\$a->[1] } (

```       [qw'beef    3.8 36'],
[qw'pork    5.4 43'],
[qw'ham     3.6 90'],
[qw'greaves 2.4 45'],
[qw'flitch  4.0 30'],
[qw'brawn   2.5 56'],
[qw'welt    3.7 67'],
[qw'salami  3.0 95'],
[qw'sausage 5.9 98'],
```

);

my (\$limit, \$value) = (15, 0);

print "item fraction weight value\n"; for (@items) {

```       my \$ratio = \$_->[1] > \$limit ? \$limit/\$_->[1] : 1;
print "\$_->[0]\t";
\$value += \$_->[2] * \$ratio;
\$limit -= \$_->[1];
if (\$ratio == 1) {
print "  all\t\$_->[1]\t\$_->[2]\n";
} else {
printf "%5.3f   %s   %8.3f\n", \$ratio, \$_->[1] * \$ratio, \$_->[2] * \$ratio;
last;
}
```

}

print "-" x 40, "\ntotal value: \$value\n"; </lang>

Output:

```item   fraction weight value
salami    all   3.0     95
ham       all   3.6     90
brawn     all   2.5     56
greaves   all   2.4     45
welt    0.946   3.5     63.378
----------------------------------------
total value: 349.378378378378
```

## Perl 6

This Solutions sorts the item by WEIGHT/VALUE <lang perl6>class KnapsackItem {

``` has \$.name;
has \$.weight is rw;
has \$.price is rw;
has \$.ppw;
```
``` method new (Str \$n, \$w, \$p) {
KnapsackItem.bless(*, :name(\$n), :weight(\$w), :price(\$p), :ppw(\$w/\$p))
}
```
``` method cut-maybe (\$max-weight) {
return False if \$max-weight > \$.weight;
\$.price = \$max-weight / \$.ppw;
\$.weight = \$.ppw * \$.price;
return True;
}
```
``` method Str () { sprintf "%8s %1.2f   %3.2f",
\$.name,
\$.weight,
\$.price }
```

}

my \$max-w = 15; say "Item Portion Value";

.say for gather

```   for < 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 >
==> map { KnapsackItem.new(\$^a, \$^b, \$^c) }
==> sort *.ppw
{
my \$last-one = .cut-maybe(\$max-w);
take \$_;
\$max-w -= .weight;
last if \$last-one;
}</lang>
```

Output:

```%perl6 knapsack_continous.p6
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
```

## PicoLisp

<lang PicoLisp>(scl 2)

(de *Items

```  ("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) )
```

(let K

```  (make
(let Weight 0
(for I (by '((L) (*/ (caddr L) -1.0 (cadr L))) sort *Items)
(T (= Weight 15.0))
(T (> Weight 15.0)
(let W (- (cadr I) Weight -15.0)
(for I K
(tab (3 -9 8 8)
NIL
(car I)
(format (caddr I) *Scl) ) )
(tab (12 8 8)
NIL
(format (sum caddr K) *Scl) ) )</lang>
```

Output:

```   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
15.00  349.38```

## Prolog

Works with SWI-Prolog and library(simplex) written by Markus Triska <lang Prolog>:- use_module(library(simplex)). % tuples (name, weights, value). knapsack :- L = [( 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)],

gen_state(S0), length(L, N), numlist(1, N, LN), ( ( create_constraint_N(LN, L, S0, S1, [], LW, [], LV), constraint(LW =< 15.0, S1, S2), maximize(LV, S2, S3) )), compute_lenword(L, 0, Len), sformat(A1, '~~w~~t~~~w|', [Len]), sformat(A2, '~~t~~2f~~~w|', [10]), sformat(A3, '~~t~~2f~~~w|', [10]), print_results(S3, A1,A2,A3, L, LN, 0, 0).

create_constraint_N([], [], S, S, LW, LW, LV, LV).

create_constraint_N([HN|TN], [(_, W, V) | TL], S1, SF, LW, LWF, LV, LVF) :- constraint([x(HN)] >= 0, S1, S2), constraint([x(HN)] =< W, S2, S3), X is V/W, create_constraint_N(TN, TL, S3, SF, [x(HN) | LW], LWF, [X * x(HN) | LV], LVF).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % compute_lenword([], N, N). compute_lenword([(Name, _, _)|T], N, NF):- atom_length(Name, L), ( L > N -> N1 = L; N1 = N), compute_lenword(T, N1, NF).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % print_results(_S, A1, A2, A3, [], [], WM, VM) :- sformat(W1, A1, [' ']), sformat(W2, A2, [WM]), sformat(W3, A3, [VM]), format('~w~w~w~n', [W1,W2,W3]).

print_results(S, A1, A2, A3, [(Name, W, V)|T], [N|TN], W1, V1) :- variable_value(S, x(N), X), ( X = 0 -> W1 = W2, V1 = V2 ; sformat(S1, A1, [Name]), sformat(S2, A2, [X]), Vtemp is X * V/W, sformat(S3, A3, [Vtemp]), format('~w~w~w~n', [S1,S2,S3]), W2 is W1 + X, V2 is V1 + Vtemp ), print_results(S, A1, A2, A3, T, TN, W2, V2).

</lang> Output :

``` ?- knapsack.
ham          3.60     90.00
greaves      2.40     45.00
brawn        2.50     56.00
welt         3.50     63.38
salami       3.00     95.00
15.00    349.38
true .```

## PureBasic

Using the greedy algorithm. <lang PureBasic>Structure item

``` name.s
weight.f   ;units are kilograms (kg)
Value.f
vDensity.f ;the density of the value, i.e. value/weight, and yes I made up the term ;)
```

EndStructure

1. maxWeight = 15

Global itemCount = 0 ;this will be increased as needed to match actual count Global Dim items.item(itemCount)

``` If itemCount >= ArraySize(items())
Redim items.item(itemCount + 10)
EndIf
With items(itemCount)
\name = name
\weight = weight
\Value = Value
If Not \weight
\vDensity = \Value
Else
\vDensity = \Value / \weight
EndIf
EndWith
itemCount + 1
```

EndProcedure

build item list

Define TotalWeight.f, TotalValue.f, i NewList knapsack.item() For i = 0 To itemCount

``` If TotalWeight + items(i)\weight < #maxWeight
knapsack() = items(i)
TotalWeight + items(i)\weight
TotalValue + items(i)\Value
Else
knapsack() = items(i)
knapsack()\weight = #maxWeight - TotalWeight
knapsack()\Value = knapsack()\weight * knapsack()\vDensity
TotalWeight = #maxWeight
TotalValue + knapsack()\Value
Break
EndIf
```

Next

If OpenConsole()

``` PrintN(LSet("Maximal weight", 26, " ") + "= " + Str(#maxWeight) + " kg")
PrintN(LSet("Total weight of solution", 26, " ") + "= " + Str(#maxWeight) + " kg")
PrintN(LSet("Total value", 26, " ") + "= " + StrF(TotalValue, 3) + " " + #CRLF\$)
PrintN("You can carry the following materials in the knapsack: ")
ForEach knapsack()
PrintN(RSet(StrF(knapsack()\weight, 1), 5, " ") + " kg  " + LSet(knapsack()\name, 10, " ") + "  (Value = " + StrF(knapsack()\Value, 3) + ")")
Next

Print(#CRLF\$ + #CRLF\$ + "Press ENTER to exit")
Input()
CloseConsole()
```

EndIf </lang> Sample output:

```Maximal weight            = 15 kg
Total weight of solution  = 15 kg
Total value               = 349.378

You can carry the following materials in the knapsack:
3.0 kg  salami      (Value = 95.000)
3.6 kg  ham         (Value = 90.000)
2.5 kg  brawn       (Value = 56.000)
2.4 kg  greaves     (Value = 45.000)
3.5 kg  welt        (Value = 63.378)```

## Python

I think this greedy algorithm of taking the largest amounts of items ordered by their value per unit weight is maximal: <lang python># NAME, WEIGHT, VALUE (for this weight) items = [("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

sorted_items = sorted(((value/amount, amount, name)

```                      for name, amount, value in items),
reverse = True)
```

wt = val = 0 bagged = [] for unit_value, amount, name in sorted_items:

```   portion = min(MAXWT - wt, amount)
wt     += portion
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```

## REXX

Any resemblence to the Fortran code is 120% coincidental. <lang rexx> /*REXX program to solve the burglar's knapsack (continuous) problem. */

@.=

``` /*  name    weight  value   */
```

@.1='flitch 4 30 ' @.2='beef 3.8 36 ' @.3='pork 5.4 43 ' @.4='greaves 2.4 45 ' @.5='brawn 2.5 56 ' @.6='welt 3.7 67 ' @.7='ham 3.6 90 ' @.8='salami 3 95 ' @.9='sausage 5.9 98 '

nL=length('total weight'); wL=length('weight'); vL=length(' value ') totW=0; totV=0

``` do j=1 while @.j\==
parse var @.j n w v .
nL=max(nL,length(n));  n.j=n
totW=totW+w         ;  w.j=w
totV=totV+v         ;  v.j=v
end
```

items=j-1 /*items is the number of items. */ nL=nL+nL%4 /*nL: max length name + 25%. */ wL=max(wL,length(format(totw,,2))) /*wL: max formatted weight width*/ vL=max(vL,length(format(totv,,2))) /*vL: max formatted value width*/ totW=0; totV=0 call show 'before sorting'

```                     /*sort items by (desending) value per unit weight.*/
```
``` do j=2 to items
k=j-1;   _n=n.j;   _w=w.j;   _v=v.j
```
```         do k=k by -1 to 1 while v.k/w.k<_v/_w
kp1=k+1;  n.kp1=n.k;  w.kp1=w.k;  v.kp1=v.k
end
```
``` kp1=k+1;  n.kp1=_n;  w.kp1=_w;  v.kp1=_v
end   /*j*/
```

call show 'after sorting' call hdr "burgler's knapsack contents" maxW=15 /*burgler's knapsack max weight. */

``` do j=1 for items while totW<maxW
if totW+w.j<maxW then do
totW=totW + w.j
totV=totV + v.j
call syf n.j, w.j, v.j
end
else do
f=(maxW-totW)/w.j
totW=totW + w.j*f
totV=totV + v.j*f
call syf n.j, w.j*f, v.j*f
end
end   /*j*/
```

call sep call sy left('total weight',nL,'-'), format(totW,,2) call sy left('total value',nL,'-'), , format(totV,,2) exit

/*─────────────────────────────────────one-liner subroutines────────────*/ hdr: indent=left(,5); call verse arg(1); call title; call sep; return sep: call sy copies('=',nL),copies("=",wL),copies('=',vL); return show: call hdr arg(1); do j=1 for items; call syf n.j,w.j,v.j;end; say; return sy: say indent left(arg(1),nL) right(arg(2),wL) right(arg(3),vL); return syf: call sy arg(1),format(arg(2),,2),format(arg(3),,2); return title: call sy center('item',nL),center("weight",wL),center('value',vL); return verse: say; say; say center(arg(1),40,'─'); say; return </lang> Output:

```
─────────────before sorting─────────────

item       weight  value
=============== ====== =======
flitch            4.00   30.00
beef              3.80   36.00
pork              5.40   43.00
greaves           2.40   45.00
brawn             2.50   56.00
welt              3.70   67.00
ham               3.60   90.00
salami            3.00   95.00
sausage           5.90   98.00

─────────────after sorting──────────────

item       weight  value
=============== ====== =======
salami            3.00   95.00
ham               3.60   90.00
brawn             2.50   56.00
greaves           2.40   45.00
welt              3.70   67.00
sausage           5.90   98.00
beef              3.80   36.00
pork              5.40   43.00
flitch            4.00   30.00

──────burgler's knapsack contents───────

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

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

1. 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
```
1. 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>```