Knapsack problem/Continuous: Difference between revisions

=={{header|Icon}} and {{header|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>

{{libheader|Icon Programming Library}}

[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides printf]

Output:<pre>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</pre>