Example 7.22: the Knapsack problem

The website http://rosettacode.org/wiki/Knapsack_Problem describes a fanciful trip by a traveler to Shangri La. They can take as many as they want of three valuable items, as long as they fit in a knapsack. The knapsack will hold no more than 25 weight units, and no more than 25 volume units. The problem is to maximize the value of the knapsack.

Item I (panacea) weighs 0.3 units, has volume 2.5 units, and value 3000 units.

Item II (ichor) weighs 0.2 units, has volume 1.5 units, and value 1800 units.

Item III (gold) weighs 2.0 units, has volume 0.2 units, and value 2500 units.

SAS

This task is straightforward to complete as a data step, in a similar fashion to that undertaken in section A.7.1. The code uses brute force, with some pruning of the space of possible items in the backpack.

data one;
   wtpanacea=0.3;    wtichor=0.2;    wtgold=2.0;
   volpanacea=0.025; volichor=0.015; volgold=0.002;
   valpanacea=3000;  valichor=1800;  valgold=2500;
   maxwt=25; maxvol=0.25;
 
   /* find upper bound for looping */
   maxpanacea = floor(min(maxwt/wtpanacea, maxvol/volpanacea));
   maxichor = floor(min(maxwt/wtichor, maxvol/volichor));
   maxgold = floor(min(maxwt/wtgold, maxvol/volgold));
   do i1 = 0 to maxpanacea; 
      do i2 = 0 to maxichor;
         do i3 = 0 to maxgold;
            panacea = i1; ichor=i2; gold=i3; 
            output;
         end;
      end;
   end;
run;

The resulting dataset one includes illegal values-- combinations with too much weight or volume. We can prune them out in a separate data set which calculates the total weight and volume implied, and discards values over the limit using the subsetting if statement (section 1.5.1). Note that these statements could have been included in the innermost do loop above. We put them in a separate data step for clarity of presentation.

data two; set one;
   vals = valpanacea*panacea + valichor*ichor + valgold*gold;
   totalweight = wtpanacea*panacea + wtichor*ichor + wtgold*gold;
   totalvolume = volpanacea*panacea + volichor*ichor + volgold*gold;
   if (totalweight le maxwt) and (totalvolume le maxvol);
run;

To find the maximum value, we can sort the data set and print the results. Here we show the top 5 values.

proc sort data=one;
   by descending vals;
run;

proc print data=one (obs=5) noobs;
   var panacea ichor gold vals totslweight;
run;

This yields the following values, leading to the conclusion that four solutions result in equal value:

panacea    ichor    gold     vals    totalweight

   0         15      11     54500        25.0
   3         10      11     54500        24.9
   6          5      11     54500        24.8
   9          0      11     54500        24.7
   1         13      11     53900        24.9

We can maximize the value at the minimum weight with 9 panacea and 11 gold.


R

The solution in R is quite similar, though a number of functions are defined to calculate the constraints and values, and expand.grid() is used to create the matrix of possible knapsack contents.

# Define consts and useful functions
weight = c(0.3, 0.2, 2.0)
volume = c(2.5, 1.5, 0.2)
value = c(3000, 1800, 2500)
maxwt = 25
maxvol = 25

# prune obviously invalid possibilities
max.items = floor(pmin(maxwt/weight, maxvol/volume))

# useful functions
getweight = function(n) sum(n*weight)
getvolume = function(n) sum(n*volume)
getvalue = function(n) sum(n*value)

# main function: return 0 if constraints not met,
# otherwise return the value of the contents, and their weight
findvalue = function(x) {
   thisweight = apply(x, 1, getweight)
   thisvolume = apply(x, 1, getvolume)
   fits = (thisweight <= maxwt) &
          (thisvolume <= maxvol)
   vals = apply(x, 1, getvalue)
   return(data.frame(I=x[,1], II=x[,2], III=x[,3],
       value=fits*vals, weight=thisweight, 
       volume=thisvolume))
}

  
# Find and evaluate all possible combinations
combs = expand.grid(lapply(max.items, function(n) seq.int(0, n)))
values = findvalue(combs)

We can display the winners in the returned data frame (section 1.1.3).

> max(values$value)
[1] 54500
> values[values$value==max(values$value),]
     I II III value weight volume
2067 9  0  11 54500   24.7   24.7
2119 6  5  11 54500   24.8   24.7
2171 3 10  11 54500   24.9   24.7
2223 0 15  11 54500   25.0   24.7

So we should prefer the solution with 9 panacea (item I), no ichor (item II), and 11 gold (item III). Happy travels!