Knapsack problem/Continuous: Difference between revisions
Added Forth (4tH) version
m (→{{header|C}}) |
(Added Forth (4tH) version) |
||
Line 432:
Take 3.5kg welt</pre>
=={{header|Forth}}==
{{trans|D}}
{{works with|4tH|3.62.0}}
<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 / ;
\ how to sort: on price/weight
:noname >r price/weight r> price/weight > ; is precedes
\ sort the index array
: setup #items 0 ?do i items (items) i th ! loop (items) #items sort ;
: knapsack ( --)
(items) begin \ use the sorted array
dup @ cell+ @c left <= \ still room in the knapsack?
while \ take all of the item, next item
." Take all of the " dup @ @c count type cr
left over @ cell+ @c - to left cell+
repeat left 100 * dup \ so how much is left?
\ if room, take as much as possible
if ." Take " . ." grams of the " @ @c count type cr else drop drop then
;
setup knapsack</lang>
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
Line 490 ⟶ 531:
end program KNAPSACK_CONTINUOUS</lang>
=={{header|Go}}==
<lang go>package main
| |||