Knapsack problem/Continuous: Difference between revisions
(→{{header|Julia}}: A new entry for Julia) |
m (→version 1: added/changed whitespace and comments, made the program safe from NOVALUE errors.) |
||
Line 2,335: | Line 2,335: | ||
===version 1=== |
===version 1=== |
||
Originally used the Fortran program as a prototype. |
Originally used the Fortran program as a prototype. |
||
<br>Some amount of code was added to |
<br>Some amount of code was added to format the output better. |
||
<lang rexx>/*REXX program solves the (continuous) burglar's knapsack problem. */ |
<lang rexx>/*REXX program solves the (continuous) burglar's knapsack problem. */ |
||
@.= /*═══════ name weight value ══════*/ |
@.= /*═══════ name weight value ══════*/ |
||
Line 2,358: | Line 2,358: | ||
call sortD /*invoke sort (which sorts descending).*/ |
call sortD /*invoke sort (which sorts descending).*/ |
||
call hdr "burglar's knapsack contents" |
call hdr "burglar's knapsack contents" |
||
do j=1 for # while totW<maxW; f=1 /*process items. */ |
|||
if totW+w.j>=maxW then f=(maxW-totW)/w.j /*calculate fract.*/ |
|||
totW=totW+w.j*f; totV=totV+v.j*f /*add ───► totals.*/ |
|||
call syf left(word('{all}',1+(f\==1)),5) n.j, w.j*f, v.j*f |
|||
end /*j*/ /* [↑] show item.*/ |
|||
call sep; say; t='t' /* [↓] $ suppresses trailing zeroes.*/ |
call sep; say; t='t' /* [↓] $ suppresses trailing zeroes.*/ |
||
call sy left('total weight',nL,'─'), $(format(totW,,d)) |
call sy left('total weight',nL,'─'), $(format(totW,,d)) |
||
call sy left('total value',nL,'─'), , $(format(totV,,d)) |
call sy left('total value',nL,'─'), , $(format(totV,,d)) |
||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
/*──────────────────────────────────one─liner subroutines─────────────────────*/ |
/*──────────────────────────────────one─liner subroutines─────────────────────*/ |
||
hdr: say; say; say center(arg(1),50,'─'); say; call title; call sep; return |
hdr: say; say; say center(arg(1),50,'─'); say; call title; call sep; return |
||
Line 2,374: | Line 2,380: | ||
syf: call sy arg(1), $(format(arg(2),,d)), $(format(arg(3),,d)); return |
syf: call sy arg(1), $(format(arg(2),,d)), $(format(arg(3),,d)); return |
||
title: call sy center('item',nL), center("weight",wL), center('value',vL);return |
title: call sy center('item',nL), center("weight",wL), center('value',vL);return |
||
$: x |
$: arg x; if pos(.,x)>1 then x=left(strip(strip(x,'T',0),,.),length(x));return x</lang> |
||
/*──────────────────────────────────SORTD subroutine──────────────────────────*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
'''output''' using the default inputs of: <tt> 15 3 </tt> |
'''output''' using the default inputs of: <tt> 15 3 </tt> |
||
<pre> |
<pre> |
Revision as of 21:04, 9 August 2015
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 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?
Ada
<lang Ada>with Ada.Text_IO; with Ada.Strings.Unbounded;
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); Ada.Text_IO.Put_Line ("Total Weight: " & Float'Image (Total_Weight (All_Items))); Ada.Text_IO.Put_Line ("Total Value: " & Float'Image (Total_Value (All_Items))); Ada.Text_IO.Put_Line ("Items:"); for I in All_Items'Range loop if All_Items (I).Taken > 0.0 then Ada.Text_IO.Put_Line (" " & Float'Image (All_Items (I).Taken) & " of " & US.To_String (All_Items (I).Name)); end if; end loop;
end Knapsack_Continuous;</lang>
BBC BASIC
<lang bbcbasic> INSTALL @lib$+"SORTSALIB"
Sort% = FN_sortSAinit(1, 0) : REM Descending nItems% = 9 maxWeight = 15.0 DIM items{(nItems%-1) name$, weight, price, worth} FOR item% = 0 TO nItems%-1 READ items{(item%)}.name$, items{(item%)}.weight, items{(item%)}.price items{(item%)}.worth = items{(item%)}.price / items{(item%)}.weight NEXT DATA "beef", 3.8, 36, "pork", 5.4, 43, "ham", 3.6, 90 DATA "greaves", 2.4, 45, "flitch", 4.0, 30, "brawn", 2.5, 56 DATA "welt", 3.7, 67, "salami", 3.0, 95, "sausage", 5.9, 98 C% = nItems% : D% = 0 CALL Sort%, items{()}, items{(0)}.worth TotalWeight = 0 TotalPrice = 0 FOR i% = 0 TO nItems%-1 IF TotalWeight + items{(i%)}.weight < maxWeight THEN TotalWeight += items{(i%)}.weight TotalPrice += items{(i%)}.price PRINT "Take all the " items{(i%)}.name$ ELSE weight = maxWeight - TotalWeight price = weight * items{(i%)}.worth TotalWeight += weight TotalPrice += price PRINT "Take "; weight " kg of " items{(i%)}.name$ EXIT FOR ENDIF NEXT PRINT '"Total weight = " ; TotalWeight " kg" PRINT "Total price = " ; TotalPrice END</lang>
Output:
Take all the salami Take all the ham Take all the brawn Take all the greaves Take 3.5 kg of welt Total weight = 15 kg Total price = 349.378379
Bracmat
<lang bracmat>( ( fixed {function to convert a rational number to fixed point notation.
The second argument is the number of decimals. } = value decimals powerOf10 . !arg:(?value.?decimals) & 10^!decimals:?powerOf10 & str $ ( div$(!value.1) "." mod $ (div$(!value+1/2*!powerOf10^-1.!powerOf10^-1).!powerOf10) ) )
& (beef.38/10.36)
(pork.54/10.43) (ham.36/10.90) (greaves.24/10.45) (flitch.40/10.30) (brawn.25/10.56) (welt.37/10.67) (salami.30/10.95) (sausage.59/10.98) : ?items
& 0:?sorteditems & whl
' ( !items:(?name.?mass.?price) ?items & (!mass*!price^-1.!mass.!name)+!sorteditems:?sorteditems )
& 0:?totalMass & :?stolenItems & whl
' ( !sorteditems:(?massPerPriceunit.?mass.?name)+?sorteditems & (!mass.!massPerPriceunit.!name) !stolenItems : ?stolenItems & !mass+!totalMass:?totalMass:~>15 )
& !stolenItems:(?mass.?massPerPriceunit.?name) ?stolenItems & 15+!mass+-1*!totalMass:?mass & (!mass.!massPerPriceunit.!name) !stolenItems:?stolenItems & 0:?totalPrice & ( !stolenItems
: ? ( (?mass.?massPerPriceunit.?name) & out$(fixed$(!mass.1) "kg of" !name) & !mass*!massPerPriceunit^-1+!totalPrice:?totalPrice & ~ ) ? | out$(fixed$(!totalPrice.2)) )
);</lang>
Output:
3.5 kg of welt 2.4 kg of greaves 2.5 kg of brawn 3.6 kg of ham 3.0 kg of salami 349.38
C
<lang c>#include <stdio.h>
- include <stdlib.h>
struct item { double w, v; const 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
Clojure
<lang Clojure>
- Solve Continuous Knapsdack Problem
- Nicolas Modrzyk
- January 2015
(def maxW 15.0) (def 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]})
(defn rob [items maxW]
(let[ val-item (fn[key] (- (/ (second (items key)) (first (items key ))))) compare-items (fn[key1 key2] (compare (val-item key1) (val-item key2))) sorted (into (sorted-map-by compare-items) items)] (loop [current (first sorted) array (rest sorted) value 0 weight 0] (let[new-weight (first (val current)) new-value (second (val current))] (if (> (- maxW weight new-weight) 0) (do (println "Take all " (key current)) (recur (first array) (rest array) (+ value new-value) (+ weight new-weight))) (let [t (- maxW weight)] ; else (println "Take " t " of " (key current) "\n" "Total Value is:" (+ value (* t (/ new-value new-weight))))))))))
(rob items maxW) </lang>
Output
Take all :salami Take all :ham Take all :brawn Take all :greaves Take 3.5 of :welt Total Value is: 349.3783783783784
Alternate Version
<lang Clojure> (def items
[{:name "beef" :weight 3.8 :price 36} {:name "pork" :weight 5.4 :price 43} {:name "ham" :weight 3.6 :price 90} {:name "graves" :weight 2.4 :price 45} {:name "flitch" :weight 4.0 :price 30} {:name "brawn" :weight 2.5 :price 56} {:name "welt" :weight 3.7 :price 67} {:name "salami" :weight 3.0 :price 95} {:name "sausage" :weight 5.9 :price 98}])
(defn per-kg [item] (/ (:price item) (:weight item)))
(defn rob [items capacity]
(let [best-items (reverse (sort-by per-kg items))] (loop [items best-items cap capacity total 0] (let [item (first items)] (if (< (:weight item) cap) (do (println (str "Take all " (:name item))) (recur (rest items) (- cap (:weight item)) (+ total (:price item)))) (println (format "Take %.1f kg of %s\nTotal: %.2f monies" cap (:name item) (+ total (* cap (per-kg item))))))))))
(rob items 15) </lang>
C++
<lang cpp>
- include<iostream>
- include<algorithm>
- 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>
Alternate Version
<lang cpp> // C++11 version
- include <iostream>
- include <vector>
- include <algorithm>
- include <string>
using namespace std;
struct item_type {
double weight, value; string name;
};
vector< item_type > 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 main() {
sort ( begin( items ), end( items ), [] (const item_type& a, const item_type& b) { return a.value / a.weight > b.value / b.weight; } );
double space = 15;
for ( const auto& item : items ) { if ( space >= item.weight ) cout << "Take all " << item.name << endl; else { cout << "Take " << space << "kg of " << item.name << endl; break; } space -= item.weight; }
} </lang>
D
<lang d>import std.stdio, std.algorithm, std.string;
struct Item {
string name; real amount, value;
@property real valuePerKG() @safe const pure nothrow @nogc { return value / amount; }
string toString() const pure /*nothrow*/ @safe { return format("%10s %7.2f %7.2f %7.2f", name, amount, value, valuePerKG); }
}
real sumBy(string field)(in Item[] items) @safe pure nothrow @nogc {
return reduce!("a + b." ~ field)(0.0L, items);
}
void main() /*@safe*/ {
const items = [Item("beef", 3.8, 36.0), Item("pork", 5.4, 43.0), Item("ham", 3.6, 90.0), Item("greaves", 2.4, 45.0), Item("flitch", 4.0, 30.0), Item("brawn", 2.5, 56.0), Item("welt", 3.7, 67.0), Item("salami", 3.0, 95.0), Item("sausage", 5.9, 98.0)] .schwartzSort!(it => -it.valuePerKG) .release;
immutable(Item)[] chosen; real space = 15.0; foreach (const 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"); writefln("%(%s\n%)", chosen); Item("TOTAL", chosen.sumBy!"amount", chosen.sumBy!"value").writeln;
}</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
Alternative Version
<lang d>void main() {
import std.stdio, std.algorithm;
static struct T { string item; double weight, price; }
auto items = [T("beef", 3.8, 36.0), T("pork", 5.4, 43.0), T("ham", 3.6, 90.0), T("greaves", 2.4, 45.0), T("flitch", 4.0, 30.0), T("brawn", 2.5, 56.0), T("welt", 3.7, 67.0), T("salami", 3.0, 95.0), T("sausage", 5.9, 98.0)] .schwartzSort!q{ -a.price / a.weight };
auto left = 15.0; foreach (it; items) if (it.weight <= left) { writeln("Take all the ", it.item); if (it.weight == left) return; left -= it.weight; } else return writefln("Take %.1fkg %s", left, it.item);
}</lang>
- Output:
Take all the salami Take all the ham Take all the brawn Take all the greaves Take 3.5kg welt
Eiffel
<lang Eiffel> class CONTINUOUS_KNAPSACK
create make
feature
make local tup: TUPLE [name: STRING; weight: REAL_64; price: REAL_64] do create tup create items.make_filled (tup, 1, 9) create sorted.make sorted.extend (-36.0 / 3.8) sorted.extend (-43.0 / 5.4) sorted.extend (-90.0 / 3.6) sorted.extend (-45.0 / 2.4) sorted.extend (-30.0 / 4.0) sorted.extend (-56.0 / 2.5) sorted.extend (-67.0 / 3.7) sorted.extend (-95.0 / 3.0) sorted.extend (-98.0 / 5.9) tup := ["beef", 3.8, 36.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["pork", 5.4, 43.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["ham", 3.6, 90.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["greaves", 2.4, 45.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["flitch", 4.0, 30.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["brawn", 2.5, 56.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["welt", 3.7, 67.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["salami", 3.0, 95.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup tup := ["sausage", 5.9, 98.0] items [sorted.index_of (- tup.price / tup.weight, 1)] := tup find_solution end
find_solution -- Solution for the continuous Knapsack Problem. local maxW, value: REAL_64 do maxW := 15 across items as c loop if maxW - c.item.weight > 0 then io.put_string ("Take all: " + c.item.name + ".%N") value := value + c.item.price maxW := maxW - c.item.weight elseif maxW /= 0 then io.put_string ("Take " + maxW.truncated_to_real.out + " kg off " + c.item.name + ".%N") io.put_string ("The total value is " + (value + (c.item.price / c.item.weight) * maxW).truncated_to_real.out + ".") maxW := 0 end end end
items: ARRAY [TUPLE [name: STRING; weight: REAL_64; price: REAL_64]]
sorted: SORTED_TWO_WAY_LIST [REAL_64]
end </lang>
- Output:
Take all: salami. Take all: ham. Take all: brawn. Take all: greaves. Take 3.5kg off welt. The total value is 349.378
Erlang
Note use of lists:foldr/2, since sort is ascending. <lang Erlang> -module( knapsack_problem_continuous ).
-export( [price_per_weight/1, select/2, task/0] ).
price_per_weight( Items ) -> [{Name, Weight, Price / Weight} || {Name, Weight, Price} <-Items].
select( Max_weight, Items ) -> {_Remains, Selected_items} = lists:foldr( fun select_until/2, {Max_weight, []}, lists:keysort(3, Items) ), Selected_items.
task() -> Items = items(), io:fwrite( "The robber takes the following to maximize the value~n" ), [io:fwrite("~.2f of ~p~n", [Weight, Name]) || {Name, Weight} <- select( 15, price_per_weight(Items) )].
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} ].
select_until( {Name, Weight, _Price}, {Remains, Acc} ) when Remains > 0 -> Selected_weight = select_until_weight( Weight, Remains ), {Remains - Selected_weight, [{Name, Selected_weight} | Acc]}; select_until( _Item, Acc ) -> Acc.
select_until_weight( Weight, Remains ) when Weight < Remains -> Weight; select_until_weight( _Weight, Remains ) -> Remains. </lang>
- Output:
11> knapsack_problem_continuous:task(). The robber takes the following to maximize the value 3.50 of "welt" 2.40 of "greaves" 2.50 of "brawn" 3.60 of "ham" 3.00 of "salami"
F#
<lang fsharp> //Fill a knapsack optimally - Nigel Galloway: February 1st., 2015 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)]
|> List.sortBy(fun(_,weight,value) -> float(-value)/weight)
let knap items maxW=
let rec take(n,g,a) = match g with | i::e -> let name, weight, value = i let total = n + weight if total <= maxW then printfn "Take all %s" name take(total, e, a+float(value)) else printfn "Take %0.2f kg of %s\nTotal value of swag is %0.2f" (maxW - n) name (a + (float(value)/weight)*(maxW - n)) | [] -> printfn "Everything taken! Total value of swag is £%0.2f; Total weight of bag is %0.2fkg" a n take(0.0, items, 0.0)
</lang>
- Output:
> knap items 15.0;; Take all salami Take all ham Take all brawn Take all greaves Take 3.50kg of welt Total value of swag is £349.38
Should your burglar be greedy, he may bring a bigger bag.
> knap items 100.0;; Take all salami Take all ham Take all brawn Take all greaves Take all welt Take all sausage Take all beef Take all pork Take all flitch Everything taken! Total value of swag is £560.00; Total weight of bag is 34.30kg
Forth
<lang forth>include lib/selcsort.4th \ use a tiny sorting algorithm
150 value left \ capacity in 1/10th kilo
create items \ list of items
," beef" 38 , 3600 , \ description, weight, price (cents) ," pork" 54 , 4300 , \ weight in 1/10 kilo ," ham" 36 , 9000 , ," greaves" 24 , 4500 , ," flitch" 40 , 3000 , ," brawn" 25 , 5600 , ," welt" 37 , 6700 , ," salami" 30 , 9500 , ," sausage" 59 , 9800 , here items - 3 / constant #items \ total number of items
- redo items swap 3 cells * + ; \ calculate address of record
- items array (items) \ array for sorting
( a -- n)
- price/weight dup 2 cells + @c swap cell+ @c / ;
- weight@ @ cell+ @c ; ( a -- n)
- .item @ @c count type cr ; ( a --)
\ how to sort: on price/weight
- noname >r price/weight r> price/weight > ; is precedes
- knapsack ( --)
(items) dup #items dup 0 ?do i items (items) i th ! loop sort begin \ use the sorted array dup weight@ left <= \ still room in the knapsack? while ." Take all of the " dup .item \ take all of the item left over weight@ - to left cell+ \ adjust knapsack, increment item repeat left 100 * dup \ so how much is left? \ if room, take as much as possible if ." Take " . ." grams of the " .item else drop drop then
knapsack</lang>
Fortran
<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 descending 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
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>
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 = putStrLn ("Take all the " ++ name) >> loop (k-weight) xs | otherwise = printf "Take %.2f kg of the %s\n" (k :: Float) name
main = 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>
See Knapsack_problem/Continuous/J for some comments on intermediate results...
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)
jq
<lang jq># continuous_knapsack(W) expects the input to be
- an array of objects {"name": _, "weight": _, "value": _}
- where "value" is the value of the given weight of the object.
def continuous_knapsack(W):
map( .price = (if .weight > 0 then (.value/.weight) else 0 end) ) | sort_by( .price ) | reverse | reduce .[] as $item # state: [array, capacity] ([[], W]; .[1] as $c | if $c <= 0 then . else ( [$item.weight, $c] | min) as $min | [.[0] + [ $item | (.weight = $min) | .value = (.price * $min)], ($c - $min) ] end) | .[1] as $remainder | .[0] | (.[] | {name, weight}), "Total value: \( map(.value) | add)", "Total weight: \(W - $remainder)" ;</lang>
The task: <lang jq>def items: [
{ "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} ];
items | continuous_knapsack(15)</lang>
- Output:
<lang sh>$ jq -r -c -n -f knapsack_continuous.jq {"name":"salami","weight":3} {"name":"ham","weight":3.6} {"name":"brawn","weight":2.5} {"name":"greaves","weight":2.4} {"name":"welt","weight":3.5000000000000004} Total value: 349.3783783783784 Total weight: 15</lang>
Julia
This solution is built around the immutable type KPCSupply
, which holds an item's data including its unit value (uvalue
). When the store's inventory is kept in this way, the solution to the continuous knapsack problem (provided by solve
), is straightforward. The thief should pack as much of the highest value items as are available until full capacity is reached, topping off with as much of the last item as the knapsack will hold. (If the store contains less than the thief's knapsack will hold, he'll take the store's entire inventory.)
An outer constructor method is used to create instances of KPCSupply
when only the item
, weight
and value
are supplied. The isless
method is provided for KPCSupply
objects so that items are transparently sorted by their unit value. KPCSupply
supports any real type for weight
, value
and uvalue
(though this simple implementation does not support mixed types or promotion). This solution uses Rational numbers to avoid rounding errors until the results are printed.
Type and Functions <lang Julia> immutable KPCSupply{S<:String, T<:Real}
item::S weight::T value::T uvalue::T
end Base.isless(a::KPCSupply, b::KPCSupply) = a.uvalue<b.uvalue
function KPCSupply{S<:String, T<:Real}(item::S, weight::T, value::T)
KPCSupply(item, weight, value, value/weight)
end
function solve{S<:String, T<:Real}(store::Array{KPCSupply{S,T},1},
capacity::T) ksack = KPCSupply{S,T}[] kweight = zero(T) for s in sort(store, rev=true) if kweight + s.weight <= capacity kweight += s.weight push!(ksack, s) else w = capacity-kweight v = w*s.uvalue push!(ksack, KPCSupply(s.item, w, v, s.uvalue)) break end end return ksack
end </lang>
Main <lang Julia> store = [KPCSupply("beef", 38//10, 36//1),
KPCSupply("pork", 54//10, 43//1), KPCSupply("ham", 36//10, 90//1), KPCSupply("greaves", 24//10, 45//1), KPCSupply("flitch", 4//1, 30//1), KPCSupply("brawn", 25//10, 56//1), KPCSupply("welt", 37//10, 67//1), KPCSupply("salami", 3//1, 95//1), KPCSupply("sausage", 59//10, 98//1)]
sack = solve(store, 15//1)
println("The store contains:") println(" Item Weight Unit Price") for s in store
println(@sprintf("%12s %4.1f %6.2f", s.item, float(s.weight), float(s.uvalue)))
end
println() println("The thief should take:") println(" Item Weight Value") for s in sack
println(@sprintf("%12s %4.1f %6.2f", s.item, float(s.weight), float(s.value)))
end w = mapreduce(x->x.weight, +, sack) v = mapreduce(x->x.value, +, sack) println(@sprintf("%12s %4.1f %6.2f",
"Total", float(w), float(v)))
</lang>
- Output:
The store contains: Item Weight Unit Price beef 3.8 9.47 pork 5.4 7.96 ham 3.6 25.00 greaves 2.4 18.75 flitch 4.0 7.50 brawn 2.5 22.40 welt 3.7 18.11 salami 3.0 31.67 sausage 5.9 16.61 The thief should take: Item Weight Value salami 3.0 95.00 ham 3.6 90.00 brawn 2.5 56.00 greaves 2.4 45.00 welt 3.5 63.38 Total 15.0 349.38
Mathematica
The problem is solved by sorting the original table by price to weight ratio, finding the accumlated weight, and the index of the item which exedes the carrying capacity (overN) The output is then all items prior to this one, along with that item corrected for it's excess weighter (overW)
<lang Mathematica>Knapsack[shop_, capacity_] := Block[{sortedTable, overN, overW, output},
sortedTable = SortBy[{#1, #2, #3, #3/#2} & @@@ shop, -#4 &]; overN = Position[Accumulate[sortedTable1 ;;, 2], a_ /; a > capacity, 1,1]1, 1; overW = Accumulate[sortedTable1 ;;, 2]overN - capacity; output = Reverse@sortedTable[[Ordering[sortedTable1 ;;, 4, -overN]]]; output-1, 2 = output-1, 2 - overW; output-1, 3 = output-1, 2 output-1, 4; Append[output1 ;;, 1 ;; 3, {"Total",Sequence @@ Total[output1 ;;, 2 ;; 3]}]]</lang>
A test using the specified data: <lang Mathematica>weightPriceTable = {{"beef", 3.8, 36}, {"pork", 5.4, 43}, {"ham", 3.6, 90}, {"greaves", 2.4, 45}, {"flitch", 4., 30}, {"brawn", 2.5, 56}, {"welt", 3.7, 67}, {"salami", 3., 95}, {"sausage", 5.9, 98}}; carryCapacity = 15; Knapsack[weightPriceTable, carryCapacity] // Grid
salami 3. 95 ham 3.6 90 brawn 2.5 56 greaves 2.4 45 welt 3.5 63.3784 Total 15. 349.378 </lang>
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>
ooRexx
version 1
<lang oorexx>/*--------------------------------------------------------------------
- 20.09.2014 Walter Pachl translated from REXX version 2
- utilizing ooRexx features like objects, array(s) and sort
- -------------------------------------------------------------------*/
maxweight = 15.0 items=.array~new items~append(.item~new('beef', 3.8, 36.0)) items~append(.item~new('pork', 5.4, 43.0)) items~append(.item~new('ham', 3.6, 90.0)) items~append(.item~new('greaves', 2.4, 45.0)) items~append(.item~new('flitch', 4.0, 30.0)) items~append(.item~new('brawn', 2.5, 56.0)) items~append(.item~new('welt', 3.7, 67.0)) items~append(.item~new('salami', 3.0, 95.0)) items~append(.item~new('sausage', 5.9, 98.0))
/* show the input */ Say '# vpu name weight value' i=0 Do x over items i+=1 Say i format(x~vpu,2,3) left(x~name,7) format(x~weight,2,3) format(x~value,3,3) End
/* sort the items by descending value per unit of weight */ items~sortWith(.DescendingComparator~new)
total_weight=0 total_value =0 Say ' ' Say 'Item Weight Value' i=0 Do x over items i+=1 Parse Var item.i name '*' weight '*' value if total_weight+x~weight<maxweight then Do total_weight = total_weight + x~weight total_value = total_value + x~value Say left(x~name,7) format(x~weight,3,3) format(x~value,3,3) End Else Do weight=maxweight-total_weight value=weight*x~vpu total_value = total_value + value total_weight = maxweight Say left(x~name,7) format(weight,3,3) format(value,3,3) Leave End End Say copies('-',23) Say 'total ' format(total_weight,4,3) format(total_value,3,3) Exit
- class item
::attribute vpu ::attribute name ::attribute weight ::attribute value
- method init
Expose vpu Use Arg name, weight, value self~name=name self~weight=weight self~value=value self~vpu=value/weight
- CLASS 'DescendingComparator' MIXINCLASS Comparator
- METHOD compare
use strict arg a, b Select
When (a~vpu)<(b~vpu) Then res='1' Otherwise res='-1' End
Return res</lang>
- Output:
# vpu name weight value 1 9.474 beef 3.800 36.000 2 7.963 pork 5.400 43.000 3 25.000 ham 3.600 90.000 4 18.750 greaves 2.400 45.000 5 7.500 flitch 4.000 30.000 6 22.400 brawn 2.500 56.000 7 18.108 welt 3.700 67.000 8 31.667 salami 3.000 95.000 9 16.610 sausage 5.900 98.000 Item Weight Value salami 3.000 95.000 ham 3.600 90.000 brawn 2.500 56.000 greaves 2.400 45.000 welt 3.500 63.378 ----------------------- total 15.000 349.378
version 2
<lang oorexx>/*--------------------------------------------------------------------
- 20.09.2014 Walter Pachl translated from REXX version 2
- utilizing ooRexx features like objects, array(s) and sort
- 21.09.2014 simplified (courtesy Rony Flatscher)
- (sort uses now the method "compareTo" defined for item)
- -------------------------------------------------------------------*/
maxweight = 15.0 items=.array~new items~append(.item~new('beef', 3.8, 36.0)) items~append(.item~new('pork', 5.4, 43.0)) items~append(.item~new('ham', 3.6, 90.0)) items~append(.item~new('greaves', 2.4, 45.0)) items~append(.item~new('flitch', 4.0, 30.0)) items~append(.item~new('brawn', 2.5, 56.0)) items~append(.item~new('welt', 3.7, 67.0)) items~append(.item~new('salami', 3.0, 95.0)) items~append(.item~new('sausage', 5.9, 98.0))
/* show the input */ Say '# vpu name weight value' i=0 Do x over items i+=1 Say i format(x~vpu,2,3) left(x~name,7) format(x~weight,2,3) format(x~value,3,3) End
/* sort the items by descending value per unit of weight */ items~sort /* using the method compareTo used for item */
total_weight=0 total_value =0 Say ' ' Say 'Item Weight Value' i=0 Do x over items i+=1 Parse Var item.i name '*' weight '*' value if total_weight+x~weight<maxweight then Do total_weight = total_weight + x~weight total_value = total_value + x~value Say left(x~name,7) format(x~weight,3,3) format(x~value,3,3) End Else Do weight=maxweight-total_weight value=weight*x~vpu total_value = total_value + value total_weight = maxweight Say left(x~name,7) format(weight,3,3) format(value,3,3) Leave End End Say copies('-',23) Say 'total ' format(total_weight,4,3) format(total_value,3,3) Exit
- class item
::attribute vpu ::attribute name ::attribute weight ::attribute value
- method init
Expose vpu Use Arg name, weight, value self~name=name self~weight=weight self~value=value self~vpu=value/weight
- method compareTo -- default sort order
Expose vpu use Arg other return -sign(vpu - other~vpu)</lang>
Output is the same as for version 1.
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)) (inc 'Weight (cadr I)) (T (> Weight 15.0) (let W (- (cadr I) Weight -15.0) (link (list (car I) W (*/ W (caddr I) (cadr I)))) ) ) (link I) ) ) ) (for I K (tab (3 -9 8 8) NIL (car I) (format (cadr I) *Scl) (format (caddr I) *Scl) ) ) (tab (12 8 8) NIL (format (sum cadr K) *Scl) (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
PL/I
<lang pli>*process source xref attributes;
KNAPSACK_CONTINUOUS: Proc Options(main); /*-------------------------------------------------------------------- * 19.09.2014 Walter Pachl translated from FORTRAN *-------------------------------------------------------------------*/ Dcl (divide,float,hbound,repeat) Builtin; Dcl SYSPRINT Print;
Dcl maxweight Dec Fixed(15,3); maxweight = 15.0; Dcl (total_weight,total_value) Dec Fixed(15,3) Init(0); Dcl vpu Dec Float(15); Dcl (i,j) Bin Fixed(31);
Dcl 1 item(9), 2 name Char(7), 2 weight Dec Fixed(15,3), 2 value Dec Fixed(15,3); Dcl temp Like item;
Call init_item(1,'beef', 3.8, 36.0); Call init_item(2,'pork', 5.4, 43.0); Call init_item(3,'ham', 3.6, 90.0); Call init_item(4,'greaves', 2.4, 45.0); Call init_item(5,'flitch', 4.0, 30.0); Call init_item(6,'brawn', 2.5, 56.0); Call init_item(7,'welt', 3.7, 67.0); Call init_item(8,'salami', 3.0, 95.0); Call init_item(9,'sausage', 5.9, 98.0);
/* sort item in descending order of their value per unit weight */ do i = 2 To hbound(item); j = i - 1; temp = item(i); do while(j>=1&item(j).value/item(j).weight<temp.value/temp.weight); item(j+1) = item(j); j = j - 1; end; item(j+1) = temp; end; Do i=1 To hbound(item); Put Edit(i,item(i))(Skip,f(2),x(2),a(7),2(f(8,3))); End; i = 0; Put Skip; Put Edit('Item Weight Value')(Skip,a); do i=1 By 1 while(i < hbound(item) & total_weight < maxweight); if total_weight+item(i).weight < maxweight then Do; total_weight = total_weight + item(i).weight; total_value = total_value + item(i).value; Put Edit(item(i))(Skip,a(7),2(f(8,3))); End; Else Do; vpu=divide(item(i).value,item(i).weight,15,8); item(i).weight=maxweight-total_weight; item(i).value=float(item(i).weight)*vpu; total_value = total_value + item(i).value; total_weight = total_weight + item(i).weight; Put Edit(item(i).name, item(i).weight, item(i).value) (Skip,a(7),2(f(8,3))); Leave Loop; end; end; Put Edit(repeat('-',22))(Skip,a); Put Edit('total',total_weight, total_value)(Skip,a(6),f(9,3),f(8,3));
init_item: Proc(i,name,weight,value); Dcl i Bin Fixed(31); Dcl name Char(*); Dcl (weight,value) Dec Fixed(15,3); item(i).name = name; item(i).weight = weight; item(i).value = value; End; End;</lang>
- Output:
1 salami 3.000 95.000 2 ham 3.600 90.000 3 brawn 2.500 56.000 4 greaves 2.400 45.000 5 welt 3.700 67.000 6 sausage 5.900 98.000 7 beef 3.800 36.000 8 pork 5.400 43.000 9 flitch 4.000 30.000 Item Weight Value salami 3.000 95.000 ham 3.600 90.000 brawn 2.500 56.000 greaves 2.400 45.000 welt 3.500 63.378 ----------------------- total 15.000 349.378
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
- maxWeight = 15
Global itemCount = 0 ;this will be increased as needed to match actual count Global Dim items.item(itemCount)
Procedure addItem(name.s, weight.f, Value.f)
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
addItem("beef", 3.8, 36) addItem("pork", 5.4, 43) addItem("ham", 3.6, 90) addItem("greaves", 2.4, 45) addItem("flitch", 4.0, 30) addItem("brawn", 2.5, 56) addItem("welt", 3.7, 67) addItem("salami", 3.0, 95) addItem("sausage", 5.9, 98) SortStructuredArray(items(), #PB_Sort_descending, OffsetOf(item\vDensity), #PB_Sort_Float, 0, itemCount - 1)
Define TotalWeight.f, TotalValue.f, i NewList knapsack.item() For i = 0 To itemCount
If TotalWeight + items(i)\weight < #maxWeight AddElement(knapsack()) knapsack() = items(i) TotalWeight + items(i)\weight TotalValue + items(i)\Value Else AddElement(knapsack()) 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 addval = portion * unit_value 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
Racket
<lang racket>#lang racket (define shop-inventory
'((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)))
(define (continuous-knapsack shop sack sack-capacity sack-total-value)
;; solved by loading up on the highest value item... (define (value/kg item) (/ (third item) (second item))) (if (zero? sack-capacity) (values (reverse sack) sack-total-value) (let* ((best-value-item (argmax value/kg shop)) (bvi-full-weight (second best-value-item)) (amount-can-take (min sack-capacity bvi-full-weight)) (bvi-full-value (third best-value-item)) (bvi-taken-value (* bvi-full-value (/ amount-can-take bvi-full-weight)))) (continuous-knapsack (remove best-value-item shop) (cons (list (first best-value-item) (if (= amount-can-take bvi-full-weight) 'all-of amount-can-take) bvi-taken-value) sack) (- sack-capacity amount-can-take) (+ sack-total-value bvi-taken-value)))))
(define (report-knapsack sack total-value)
(for-each (lambda (item) (if (eq? 'all-of (second item)) (printf "Take all of the ~a (for ~a)~%" (first item) (third item)) (printf "Take ~a of the ~a (for ~a)~%" (real->decimal-string (second item)) (first item) (real->decimal-string (third item))))) sack) (printf "For a grand total of: ~a" (real->decimal-string total-value)))
(call-with-values (lambda () (continuous-knapsack shop-inventory null 15 0))
report-knapsack)</lang>
- Output:
Take all of the salami (for 95.0) Take all of the ham (for 90.0) Take all of the brawn (for 56.0) Take all of the greaves (for 45.0) Take 3.50 of the welt (for 63.38) For a grand total of: 349.38
REXX
version 1
Originally used the Fortran program as a prototype.
Some amount of code was added to format the output better.
<lang rexx>/*REXX program solves the (continuous) burglar's knapsack 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 '
parse arg maxW d . /*get possible arguments from the C.L. */ if maxW== | maxW==',' then maxW=15 /*the burglar's knapsack maximum weight*/ if d== | d==',' then d= 3 /*number of decimal digits in FORMAT. */ wL=d+length('weight'); nL=d+length('total weight'); vL=d+length('value') totW=0; totV=0
do #=1 while @.#\==; parse var @.# n.# w.# v.# . end /*#*/ /* [↑] assign item to separate lists. */
- =#-1 /*#: is the number of items in @ list.*/
call show 'unsorted item list' /*display the header and the @ list.*/ call sortD /*invoke sort (which sorts descending).*/ call hdr "burglar's knapsack contents"
do j=1 for # while totW<maxW; f=1 /*process items. */ if totW+w.j>=maxW then f=(maxW-totW)/w.j /*calculate fract.*/ totW=totW+w.j*f; totV=totV+v.j*f /*add ───► totals.*/ call syf left(word('{all}',1+(f\==1)),5) n.j, w.j*f, v.j*f end /*j*/ /* [↑] show item.*/
call sep; say; t='t' /* [↓] $ suppresses trailing zeroes.*/ call sy left('total weight',nL,'─'), $(format(totW,,d)) call sy left('total value',nL,'─'), , $(format(totV,,d)) exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ sortD: do s=2 to #; a=n.s; !=w.s; u=v.s /* [↓] this is a descending sort.*/
do k=s-1 by -1 to 1 while v.k/w.k1 then x=left(strip(strip(x,'T',0),,.),length(x));return x</lang>
output using the default inputs of: 15 3
────────────────unsorted item list──────────────── item weight value ═══════════════ ═════════ ════════ flitch 4 30 beef 3.8 36 pork 5.4 43 greaves 2.4 45 brawn 2.5 56 welt 3.7 67 ham 3.6 90 salami 3 95 sausage 5.9 98 ───────────burglar's knapsack contents──────────── item weight value ═══════════════ ═════════ ════════ {all} salami 3 95 {all} ham 3.6 90 {all} brawn 2.5 56 {all} greaves 2.4 45 welt 3.5 63.378 ═══════════════ ═════════ ════════ total weight─── 15 total value─── 349.378
version 2
<lang rexx> /*--------------------------------------------------------------------
* 19.09.2014 Walter Pachl translated from FORTRAN * While this program works with all REXX interpreters, * see section ooRexx for a version that utilizes the ooRexx features *-------------------------------------------------------------------*/ maxweight = 15.0 input.0=0 Call init_input 'beef', 3.8, 36.0 Call init_input 'pork', 5.4, 43.0 Call init_input 'ham', 3.6, 90.0 Call init_input 'greaves', 2.4, 45.0 Call init_input 'flitch', 4.0, 30.0 Call init_input 'brawn', 2.5, 56.0 Call init_input 'welt', 3.7, 67.0 Call init_input 'salami', 3.0, 95.0 Call init_input 'sausage', 5.9, 98.0
/* sort the items by descending value per unit of weight */ Do i = 1 to input.0 Parse Var input.i name '*' weight '*' value vpu=value/weight; If i=1 Then Do item.0=1 item.1=input.1 vpu.1=vpu End Else Do Do ii=1 To item.0 If vpu.ii<vpu Then Leave End Do jj=item.0 To ii By -1 jj1=jj+1 item.jj1=item.jj vpu.jj1=vpu.jj End item.ii=input.i vpu.ii=vpu item.0=item.0+1 End End Say '# vpu name weight value' Do i=1 To item.0 Parse Var item.i name '*' weight '*' value Say i format(vpu.i,2,3) left(name,7) format(weight,2,3) format(value,3,3) End
total_weight=0 total_value =0 Say ' ' Say 'Item Weight Value' Do i=1 To item.0 Parse Var item.i name '*' weight '*' value if total_weight+weight < maxweight then Do total_weight = total_weight + weight total_value = total_value + value Say left(name,7) format(weight,3,3) format(value,3,3) End Else Do weight=maxweight-total_weight value=weight*vpu.i total_value = total_value + value total_weight = maxweight Say left(name,7) format(weight,3,3) format(value,3,3) Leave End End Say copies('-',23) Say 'total ' format(total_weight,4,3) format(total_value,3,3) Exit
init_input: Procedure Expose input.
Parse Arg name,weight,value i=input.0+1 input.i=name'*'weight'*'value input.0=i Return</lang>
- Output:
# vpu name weight value 1 31.667 salami 3.000 95.000 2 25.000 ham 3.600 90.000 3 22.400 brawn 2.500 56.000 4 18.750 greaves 2.400 45.000 5 18.108 welt 3.700 67.000 6 16.610 sausage 5.900 98.000 7 9.474 beef 3.800 36.000 8 7.963 pork 5.400 43.000 9 7.500 flitch 4.000 30.000 Item Weight Value salami 3.000 95.000 ham 3.600 90.000 brawn 2.500 56.000 greaves 2.400 45.000 welt 3.500 63.378 ----------------------- total 15.000 349.378
Ruby
<lang ruby>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] ].sort_by{|item, weight, price| -price / weight}
maxW, value = 15.0, 0 items.each do |item, weight, price|
if (maxW -= weight) > 0 puts "Take all #{item}" value += price else puts "Take %gkg of %s" % [t=weight+maxW, item], "", "Total value of swag is %g" % (value+(price/weight)*t) break end
end</lang>
- Output:
Take all salami Take all ham Take all brawn Take all greaves Take 3.5kg of welt Total value of swag is 349.378
Run BASIC
<lang runbasic>dim name$(9) dim wgt(9) dim price(9) dim tak$(100)
name$(1) = "beef" : wgt(1) = 3.8 : price(1) = 36 name$(2) = "pork" : wgt(2) = 5.4 : price(2) = 43 name$(3) = "ham" : wgt(3) = 3.6 : price(3) = 90 name$(4) = "greaves" : wgt(4) = 2.4 : price(4) = 45 name$(5) = "flitch" : wgt(5) = 4.0 : price(5) = 30 name$(6) = "brawn" : wgt(6) = 2.5 : price(6) = 56 name$(7) = "welt" : wgt(7) = 3.7 : price(7) = 67 name$(8) = "salami" : wgt(8) = 3.0 : price(8) = 95 name$(9) = "sausage" : wgt(9) = 5.9 : price(9) = 98
for beef = 0 to 15 step 3.8
for pork = 0 to 15 step 5.4 for ham = 0 to 15 step 3.6 for greaves = 0 to 15 step 2.4 for flitch = 0 to 15 step 4.0 for brawn = 0 to 15 step 2.5 for welt = 0 to 15 step 3.7 for salami = 0 to 15 step 3.0 for sausage = 0 to 15 step 5.9 if beef + pork + ham + greaves + flitch + brawn + welt + salami + sausage <= 15 then totPrice = 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 if totPrice >= maxPrice then maxPrice = totPrice theMax = max(totPrice,maxPrice) t = t + 1 tak$(t) = str$(maxPrice);",";beef;",";pork;",";ham;",";greaves;",";flitch;",";brawn;",";welt;",";salami;",";sausage end if end if
next:next :next :next :next :next :next :next :next
print "Best 2 Options":print for i = t-1 to t
totTake = val(word$(tak$(i),1,",")) if totTake > 0 then totWgt = 0 for j = 2 to 10 wgt = val(word$(tak$(i),j,",")) totWgt = totWgt + wgt value = wgt / wgt(j - 1) * price(j - 1) if wgt <> 0 then print name$(j-1);chr$(9);"Value: ";using("###.#",value);chr$(9);"Weight: ";using("##.#",wgt) next j print "-------- Total ";using("###.#",totTake);chr$(9);"Weight: ";totWgt end if
next i</lang>Output:
Best 2 Options salami Value: 285.0 Weight: 9.0 sausage Value: 98.0 Weight: 5.9 -------- Total 383.0 Weight: 14.9 salami Value: 475.0 Weight: 15.0 -------- Total 475.0 Weight: 15.0
Sidef
<lang ruby>var 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],
].sort {|a,b| b[2]/b[1] <=> a[2]/a[1] };
var (limit, value) = (15, 0); print "Item Fraction Weight Value\n";
items.each { |item|
var ratio = (item[1] > limit ? limit/item[1] : 1); value += item[2]*ratio; limit -= item[1]; if (ratio == 1) { printf("%-8s %4s %7.2f %6.2f\n", item[0], 'all', item[1], item[2]); } else { printf("%-8s %-4.2f %7.2f %6.2f\n", item[0], ratio, item[1]*ratio, item[2]*ratio); break; }
};
say "#{'-'*28}\ntotal value: #{'%.14g' % value }";</lang>
- Output:
Item Fraction Weight Value salami all 3.00 95.00 ham all 3.60 90.00 brawn all 2.50 56.00 greaves all 2.40 45.00 welt 0.95 3.50 63.38 ---------------------------- total value: 349.37837837838
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>
XPL0
<lang XPL0>int Name, Price, I, BestItem; real Weight, Best, ItemWt, TotalWt; def Items = 9; real PricePerWt(Items); int Taken(Items); include c:\cxpl\codes;
[Name:= ["beef","pork","ham","greaves","flitch","brawn","welt","salami","sausage"]; Weight:= [ 3.8, 5.4, 3.6, 2.4, 4.0, 2.5, 3.7, 3.0, 5.9]; Price:= [ 36, 43, 90, 45, 30, 56, 67, 95, 98];
for I:= 0 to Items-1 do
[PricePerWt(I):= float(Price(I)) / Weight(I); Taken(I):= false; ];
Format(2,1); TotalWt:= 0.0; repeat Best:= 0.0;
for I:= 0 to Items-1 do if not Taken(I) and PricePerWt(I) > Best then [Best:= PricePerWt(I); BestItem:= I]; Taken(BestItem):= true; \take item ItemWt:= Weight(BestItem); \get its weight TotalWt:= TotalWt + ItemWt; \add to total weight if TotalWt > 15.0 then \if total is too much, reduce ItemWt:= ItemWt - (TotalWt-15.0); \item weight by amount it's over RlOut(0, ItemWt); Text(0, " kg of "); \show weight and item Text(0, Name(BestItem)); CrLf(0);
until TotalWt >= 15.0; \all we can steal ]</lang>
Output:
3.0 kg of salami 3.6 kg of ham 2.5 kg of brawn 2.4 kg of greaves 3.5 kg of welt
zkl
<lang zkl>items:=List( T(3.8, 36.0, "beef"), T(5.4, 43.0, "pork"), // weight, value, name T(3.6, 90.0, "ham"), T(2.4, 45.0, "greaves"), T(4.0, 30.0, "flitch"),T(2.5, 56.0, "brawn"), T(3.7, 67.0, "welt"), T(3.0, 95.0, "salami"), T(5.9, 98.0, "sausage"), ); fcn item_cmp(a,b){ a[1]/a[0] > b[1]/b[0] }
items.sort(item_cmp); space := 15.0; foreach it in (items){ w,_,nm:=it;
if (space >= w){ println("take all ",nm); space-=w } else{ println("take %gkg of %gkg of %s".fmt(space,w,nm)); break }
}</lang>
- Output:
take all salami take all ham take all brawn take all greaves take 3.5kg of 3.7kg of welt
- Programming Tasks
- Classic CS problems and programs
- Ada
- BBC BASIC
- Bracmat
- C
- Clojure
- C++
- D
- Eiffel
- Erlang
- F Sharp
- Forth
- Fortran
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- Jq
- Julia
- Mathematica
- Mathprog
- OCaml
- OoRexx
- Perl
- Perl 6
- PicoLisp
- PL/I
- Prolog
- PureBasic
- Python
- Racket
- REXX
- Ruby
- Run BASIC
- Sidef
- Tcl
- Ursala
- XPL0
- Zkl
- Puzzles
- GUISS/Omit