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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
# Test: perl6 ch2.p6
use v6.d;
# Box configurations
my %boxes = (
R => { weight => 1, amount => 1 },
B => { weight => 1, amount => 2 },
G => { weight => 2, amount => 2 },
Y => { weight => 12, amount => 4 },
P => { weight => 4, amount => 10 },
);
sub MAIN () {
# knapsack with unlimited boxes and 15 kg max
knapsack(%boxes, 15, Inf);
# knapsack with 2 3 4 boxes and 15kg max
knapsack(%boxes, 15, 2);
knapsack(%boxes, 15, 3);
knapsack(%boxes, 15, 4);
}
sub knapsack (%boxes, Int $max_weight, Num() $max_boxes) {
my $total_weight = 0;
my $total_boxes = 0;
my $total_amount = 0;
my $set_of_boxes = '';
for %boxes.keys.sort(&sort-value-weight) -> $key {
my $box = %boxes.{$key};
# While there is space or weight left
while (1) {
# Check for space or weight
last unless
$total_weight + $box.{'weight'} <=
$max_weight;
last unless
!$max_boxes ||
($max_boxes && $total_boxes + 1 <=
$max_boxes);
$total_boxes++;
$set_of_boxes ~= $key;
$total_weight += $box.{'weight'};
$total_amount += $box.{'amount'};
}
}
say 'Max weight: ' ~ $max_weight ~
', max boxes: ' ~ $max_boxes ~
'. Boxes in knapsack: ' ~
$set_of_boxes ~
' ' ~ $total_weight ~ 'kg ' ~
'£' ~ $total_amount;
}
# Sort function to sort by value then weight
sub sort-value-weight {
my $value_a =
%boxes.{$^a}.{'amount'} /
%boxes.{$^a}.{'weight'};
my $value_b =
%boxes.{$^b}.{'amount'} /
%boxes.{$^b}.{'weight'};
my $weight_a =
%boxes.{$^a}.{'weight'};
my $weight_b =
%boxes.{$^b}.{'weight'};
if ( $value_b > $value_a ) {
return 1;
} elsif ( $value_b == $value_a ) {
return ($weight_b > $weight_a) ?? 1 !! -1;
} else {
return -1;
}
}
|
