blob: 3352993dbbfc59dcf6301d7a4f5208fa4445bdd8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
# Numbers worked out in one event (Pure 018): a square root by Newton's
# steps, stopping when they stop shrinking, and the best a knapsack holds,
# its table an event's list.
record Item {
id = 0
weight = 0
worth = 0
}
record Cell {
at = 0
best = 0
}
state items: list of Item by id
state root = 0
state steps = 0
state packed = 0
input stock = message {
id: u32
weight: u32
worth: u32
}
input sqrt = message {
x: number
}
input pack = message {
capacity: u32
}
on stock {
items.add(Item { id: stock.id, weight: stock.weight, worth: stock.worth })
}
on sqrt {
let r = if sqrt.x > 1 { sqrt.x } else { 1 }
steps = 0
for i in 0 .. 200 {
let next = (r + sqrt.x / r) / 2
if next >= r { break }
r = next
steps = steps + 1
}
root = r
}
on pack {
let table: list of Cell by at
for c in 0 .. pack.capacity + 1 {
table.add(Cell { at: c })
}
for it in items {
for k in 0 .. pack.capacity + 1 {
let c = pack.capacity - k
if c >= it.weight {
let with = table[c - it.weight].best + it.worth
if with > table[c].best { table[c].best = with }
}
}
}
packed = table[pack.capacity].best
}
view answer = "root {root} in {steps} steps, packed {packed}"
|
