25 October 2026

Challenge 036

A Sackfull of Nuts

• Task 2: Knapsack problem

Task 2: Knapsack problem

Write a program to solve Knapsack Problem.

There are 5 color coded boxes with varying weights and amounts in GBP. Which boxes should be choosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kgs?

R: (weight = 1 kg, amount = £1)
B: (weight = 1 kg, amount = £2)
G: (weight = 2 kg, amount = £2)
Y: (weight = 12 kg, amount = £4)
P: (weight = 4 kg, amount = £10)

Bonus task, what if you were allowed to pick only 2 boxes or 3 boxes or 4 boxes? Find out which combination of boxes is the most optimal?

---

Solution

I’ll take a sledgehammer to crack the nut.

Given \(n\) items having weights \(w_i\) and amounts \(a_i\), select a subset of these items such that the number of selected items does not exceed \(c\) and the total weight of the selected items does not exceed \(l\). Find a selection of items that fulfills the above conditions and that has a maximum total amount.

Introducing variables \(x_i\) where

\[x_i = \begin{cases} 1& \text{if item } i \text{ is selected}\\ 0& \text{otherwise} \end{cases}\]

the problem may be regarded as the integer linear program (ILP):

\[\begin{alignat*}{2} \text{Maximize:}&&\sum_{i=1}^n a_i x_i& \\ \text{subject to:}&& \sum_{i=1}^n w_i x_i &\le l \\ &&\sum_{i=1}^n x_i &\le c \\ &&x_i &\in \{0, 1\} \text{ for } 1 \le i \le n \end{alignat*}\]

Using PDL::Opt::GLPK, the ILP may be solved with the following function:

use strict;
use warnings;
use experimental 'signatures';
use PDL;
use PDL::Opt::GLPK;

sub knapsack ($name, $maxcount, $maxweight, $weight, $amount) {
    die "invalid number of weights" if @$name != @$weight;
    die "invalid number of amounts" if @$name != @$amount;
    my $c = pdl $amount;
    my $a = pdl $weight, ones($c);
    my $b = pdl $maxweight, $maxcount;
    my $ctype = pdl GLP_UP * ones($a->dim(1));
    my $vtype = pdl GLP_BV * ones($c);
    glpk($c, $a, $b, zeroes($c), zeroes($c), $ctype, $vtype, GLP_MAX,
        my $xopt = null, my $fopt = null, my $status = null);
    die "status: $status" if $status != GLP_OPT;
    (\my %name)->@{@$name} = $xopt->list;

    grep $name{$_}, @$name;
}

Calling it from the shell:

$ ./ch-2.pl -name R B G Y P -count 5 -limit 15 -weight 1 1 2 12 4 -amount 1 2 2 4 10 
R B G P
$ ./ch-2.pl -name R B G Y P -count 2 -limit 15 -weight 1 1 2 12 4 -amount 1 2 2 4 10 
B P
$ ./ch-2.pl -name R B G Y P -count 3 -limit 15 -weight 1 1 2 12 4 -amount 1 2 2 4 10 
B G P

See the full solution to task 2.