Rosetta Code

Knapsack problem/Continuous: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Hansoft (talk | contribs)
374 edits
Added Forth (4tH) version
Hansoft (talk | contribs)
374 edits
Some optimization in Forth example
Line 456:
( 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
\ sort the index array
: setup #items 0 ?do i items (items) i th ! loop (items) #items sort ;
 
: knapsack ( --)
(items) begindup #items dup 0 ?do i items (items) i th ! loop \ use the sorted arraysort
begin dup @ cell+ @c left <= \ still room in \ use the knapsack?sorted array
while dup weight@ left <= \ takestill allroom ofin the item, next itemknapsack?
while
." Take all of the " dup @.item @c count type cr\ take all of the item
left over @ cell+ @c - to left cell+
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 " @ @c count type cr.item else drop drop then
;
 
setup knapsack</lang>
 
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Continuous"