Wednesday, January 13, 2010

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!

7 comments:

Anonymous said...

Or, if you don't want to loop over all combinations, you can set up a general linear programming problem and solve it using lpsolve from R, http://lpsolve.sourceforge.net/5.5/R.htm

Paddy3118 said...

How about giving back?

Rather than just quoting Rosetta Code problems for your own book why don't you join in and add SAS and R solutions to many more of the problems on the Rosetta Code site?

I am sure you would be made welcome - They made me welcome, and I'm difficult!

- Paddy.

Ken Kleinman said...

Thanks for reading, and for the suggestion, Paddy. Speaking for myself, I'm not a computer scientist. I'm a little intimidated by Rosetta Code and I don't feel competent to address the things I think are important to that community. I believe that Nick did contribute his R approach to the Knapsack problem discussed above, but I could be wrong.

Rhonalen said...

hey, thank you. we needed these infos for a paper. i hope it's okay to use them. =)

Ken Kleinman said...

Happy to help. Just remember to attribute correctly, so your Professor knows what's yours and what's not your own work.

Anonymous said...

im an industrial engineer and i need to understand this knapsack problem. but i cant it. how can you do ?

Angus Davidson said...

Thanks for this. Helpful for someone like me just beginning with R.

Off topic but I was wondering if you could recommend any training providers in London. I work for an I Bank and so can get training budget for a couple of days of dedicated training. Just wondering if you had any thoughts?