82 lines
2.9 KiB
Plaintext
82 lines
2.9 KiB
Plaintext
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
|