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:

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

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.

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.

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

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

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

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?

Post a Comment