Knapsack problem/Continuous: Difference between revisions

{{trans|Fortran}}

Using QuickSort (a generic form, non recursive)

=={{header|M2000 Interpreter}}==

<lang M2000 Interpreter>

Module Knapsack {

Form 60, 40

Cls 5, 0

Pen 14

Class Quick {

Private:

partition=lambda-> {

Read &A(), p, r : i = p-1 : x=A(r)

For j=p to r-1 {If .LE(A(j), x) Then i++:Swap A(i),A(j)

} : Swap A(i+1), A(r) : Push i+2, i

}

Public:

LE=Lambda->Number<=Number

\\ module for strings erased here

Function quicksort {

Read ref$

{

loop : If Stackitem() >= Stackitem(2) Then Drop 2 : if empty then {Break} else continue

over 2,2 : call .partition(ref$) :shift 3

}

}

}

Class Item {

name$, weight, aValue ' can't use Value has other meaning

class:

Module Item (.name$, .weight, .aValue) {}

}

Def Double max_weight=15, total_weight, total_value, frac

Def long I

Dim Items(1 to 9)

Flush ' empty stack

\\ now fill stack

Data "beef", 3.8, 36,"pork", 5.4, 43,"ham", 3.6, 90, "greaves", 2.4, 45, "flitch", 4, 30

Data "brawn", 2.5, 56, "welt", 3.7, 67, "salami", 3, 95, "sausage", 5.9, 98

For i=1 to 9 : Items(i)=Item(Letter$, Number, Number): Next i

\\ Setup QuickSort

Quick=Quick()

Quick.LE=lambda (b, a)-> {

=a.avalue/a.weight<=b.avalue/b.weight

}

Call Quick.QuickSort(&items(), 1, 9)

\\ So now we have a sorted array of objects

i=0

\\ Setup console to print

Dim Back(-1 to 0)

Back(-1)=#666666, #444444

Alter=True

\\ $("0.00", 20) Set number rounding for print, and 14 chars column width

\\ $(2) set center justify for non proportional print

\\ $(0) set default - strings justify left, numbers right

Print $("0.00", 20),$(2),"", "Knapsack"

Pen 0 {

Print @(pos, row,width,row+1, 7),"Item", "Weight (Kg)", "Price (value)", $(0)

}

While i<Len(Items()) and total_weight<max_weight {

i++

if total_weight+items(i).weight<max_weight Then {

total_weight+=items(i).weight

total_value+=items(i).avalue

WriteItem(i, 1)

} Else {

frac=(max_weight-total_weight)/items(i).weight

total_weight+=items(i).weight*frac

total_value+=items(i).avalue*frac

WriteItem(i, frac )

}

}

Print

Pen 0 {

Print @(pos+1, row,width,row+1, 7, 7), "Total Weight",total_weight

Print @(pos+1, row,width,row+1, 7, 7), "Total Value", total_value

}

End

Sub WriteItem(i, frac)

For Items(i) {

Print @(pos+1, row,width,row+1, back(alter), 14), .name$, .weight*frac, .avalue*frac

Alter~

}

End Sub

}

Knapsack

</lang>

Output the same as other examples, with some color.