Anonymous user
Knapsack problem/Continuous: Difference between revisions
→{{header|Ursala}}
(added Ursala) |
|||
Line 377:
=={{header|Ursala}}==
We might as well leave this one to the experts by setting it up as a
[http://en.wikipedia.org/wiki/Linear_programming linear programming] problem and handing it off to an external library (which will be either [http://sourceforge.net/projects/lpsolve lpsolve] or
[http://www.gnu.org/software/glpk/glpk.html gkpk] depending on the run-time system configuration).
<lang Ursala>#import std
#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 =
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, # values divided by weights, negated so as to maximize
equations: ~&iNC\15.+ 1.-*@nS] # 1 equation constraining the total weight to 15
#cast %em
main = ^p(pad` @nS,~&mS) solution system items</lang>
output:
<pre>
<
'brawn ': 2.500000e+00,
'greaves': 2.400000e+00,
'ham ': 3.600000e+00,
'salami ': 3.000000e+00,
'welt ': 3.500000e+00></pre>
| |||