Knapsack problem/Bounded: Difference between revisions
Content deleted Content added
m →{{header|Picat}}: Adding {{out}} |
Knapsack problem/Bounded in FreeBASIC |
||
Line 1,130: | Line 1,130: | ||
→ 10827 ;; # of entries in cache |
→ 10827 ;; # of entries in cache |
||
</lang> |
</lang> |
||
=={{header|FreeBASIC}}== |
|||
<lang freebasic>#define PesoMax 400 |
|||
#define items 22 |
|||
#define Tabu Chr(9) |
|||
Type Knapsack |
|||
articulo As String*22 |
|||
peso As Integer |
|||
valor As Integer |
|||
pieza As Integer |
|||
End Type |
|||
Dim item(1 To 22) As Knapsack => { _ |
|||
("map ", 9, 150, 0), ("compass ", 13, 35, 0), _ |
|||
("water ", 153, 200, 0), ("sandwich ", 50, 160, 0), _ |
|||
("glucose ", 15, 60, 0), ("tin ", 68, 45, 0), _ |
|||
("banana ", 27, 60, 0), ("apple ", 39, 40, 0), _ |
|||
("cheese ", 23, 30, 0), ("beer ", 52, 10, 0), _ |
|||
("suntan cream ", 11, 70, 0), ("camera ", 32, 30, 0), _ |
|||
("T-shirt ", 24, 15, 0), ("trousers ", 48, 10, 0), _ |
|||
("umbrella ", 73, 40, 0), ("waterproof trousers ", 42, 70, 0), _ |
|||
("waterproof overclothes", 43, 75, 0), ("note-case ", 22, 80, 0), _ |
|||
("sunglasses ", 7, 20, 0), ("towel ", 18, 12, 0), _ |
|||
("socks ", 4, 50, 0), ("book ", 30, 10, 0)} |
|||
Dim As Integer i, tot = 0, TValor = 0 |
|||
For i =1 To Ubound(item) |
|||
tot += item(i).peso |
|||
Next i |
|||
Dim As Integer TPeso = tot-PesoMax |
|||
Dim As String pr = "" |
|||
Dim As Integer c = 0, v, w, k |
|||
Do |
|||
v = 1e9 : w = 0 : k = 0 |
|||
For i = 1 To items |
|||
If item(i).pieza = 0 Then |
|||
w = 1000 * item(i).valor / item(i).peso |
|||
If w < v Then v = w : k = i |
|||
End If |
|||
Next i |
|||
If k Then |
|||
TPeso -= item(k).peso |
|||
item(k).pieza = 1 |
|||
If TPeso <= 0 Then Exit Do |
|||
End If |
|||
c += 1 |
|||
Loop Until c>= items |
|||
Print "Knapsack contents: " |
|||
For i = 1 To items |
|||
If item(i).pieza = 0 Then |
|||
Print item(i).articulo & Tabu & item(i).peso & Tabu & item(i).valor |
|||
TValor += item(i).valor |
|||
End If |
|||
Next i |
|||
Print !"\nTotal value: "; TValor |
|||
Print "Total weight: "; PesoMax + TPeso |
|||
Sleep</lang> |
|||
{{out}} |
|||
<pre>Knapsack contents: |
|||
map 9 150 |
|||
compass 13 35 |
|||
water 153 200 |
|||
sandwich 50 160 |
|||
glucose 15 60 |
|||
banana 27 60 |
|||
suntan cream 11 70 |
|||
waterproof trousers 42 70 |
|||
waterproof overclothes 43 75 |
|||
note-case 22 80 |
|||
sunglasses 7 20 |
|||
socks 4 50 |
|||
Total value: 1030 |
|||
Total weight: 396</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |