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
84
85
86
|
#!/usr/bin/perl
# Test: ./ch2.pl
use strict;
use warnings;
# 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 },
};
# knapsack with unlimited boxes and 15 kg max
knapsack($boxes, 15, 0);
# knapsack with 2 3 4 boxes and 15kg max
knapsack($boxes, 15, 2);
knapsack($boxes, 15, 3);
knapsack($boxes, 15, 4);
sub knapsack {
my ($boxes, $max_weight, $max_boxes) = @_;
my $total_weight = 0;
my $total_boxes = 0;
my $total_amount = 0;
my $set_of_boxes;
# Order the boxes by which
# gives the most value, followed by weight.
for my $key ( sort sort_value_weight keys %$boxes ) {
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};
}
}
print 'Max weight: ' . $max_weight;
print ', max boxes: ' . $max_boxes
if ($max_boxes);
print '. Boxes in knapsack: ' .
$set_of_boxes;
print ' ' . $total_weight . 'kg ';
print '£' . $total_amount . "\n";
}
# 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;
}
}
|
