Knapsack problem/Unbounded: Difference between revisions
(added ocaml) |
|||
| Line 915: | Line 915: | ||
| hd::tl -> |
| hd::tl -> |
||
let acc = |
let acc = |
||
List. |
List.concat |
||
( |
(List.map |
||
(fun l -> |
|||
List.map (fun v -> (v::l)) hd |
|||
) acc |
|||
) |
|||
in |
in |
||
aux acc tl |
aux acc tl |
||
Revision as of 20:58, 16 December 2009
You are encouraged to solve this task according to the task description, using any language you may know.
A traveller gets diverted and has to make an unscheduled stop in what turns out to be Shangri La. Opting to leave, he is allowed to take as much as he likes of the following items, so long as it will fit in his knapsack, and he can carry it. He knows that he can carry no more than 25 'weights' in total; and that the capacity of his knapsack is 0.25 'cubic lengths'.
Looking just above the bar codes on the items he finds their weights and volumes. He digs out his recent copy of a financial paper and gets the value of each item.
| Item | Explanation | Value (each) | weight | Volume (each) |
| panacea (vials of) | Incredible healing properties | 3000 | 0.3 | 0.025 |
| ichor (ampules of) | Vampires blood | 1800 | 0.2 | 0.015 |
| gold (bars) | Shiney shiney | 2500 | 2.0 | 0.002 |
| Knapsack | For the carrying of | - | <=25 | <=0.25 |
He can only take whole units of any item, but there is much more of any item than he could ever carry
How many of each item does he take to maximise the value of items he is carrying away with him?
Note:
- There are four solutions that maximise the value taken. Only one need be given.
ALGOL 68
<lang algol68>MODE BOUNTY = STRUCT(STRING name, INT value, weight, volume);
[]BOUNTY items = (
("panacea", 3000, 3, 25),
("ichor", 1800, 2, 15),
("gold", 2500, 20, 2)
);
BOUNTY sack := ("sack", 0, 250, 250);
OP * = ([]INT a,b)INT: ( # dot product operator #
INT sum := 0; FOR i TO UPB a DO sum +:= a[i]*b[i] OD; sum
);
OP INIT = (REF[]INT vector)VOID:
FOR index FROM LWB vector TO UPB vector DO
vector[index]:=0
OD;
OP INIT = (REF[,]INT matrix)VOID:
FOR row index FROM LWB matrix TO UPB matrix DO
INIT matrix[row index,]
OD;
PROC total value = ([]INT items count, []BOUNTY items, BOUNTY sack) STRUCT(INT value, weight, volume):(
### Given the count of each item in the sack return -1 if they can"t be carried or their total value.
(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
###
INT weight = items count * weight OF items;
INT volume = items count * volume OF items;
IF weight > weight OF sack OR volume > volume OF sack THEN
(-1, 0, 0)
ELSE
( items count * value OF items, -weight, -volume)
FI
);
PRIO WRAP = 5; # wrap negative array indices as per python's indexing regime # OP WRAP = (INT index, upb)INT:
IF index>=0 THEN index ELSE upb + index + 1 FI;
PROC knapsack dp = ([]BOUNTY items, BOUNTY sack)[]INT:(
### Solves the Knapsack problem, with two sets of weights, using a dynamic programming approach ###
# (weight+1) x (volume+1) table # # table[w,v] is the maximum value that can be achieved # # with a sack of weight w and volume v. # # They all start out as 0 (empty sack) # [0:weight OF sack, 0:volume OF sack]INT table; INIT table;
FOR w TO 1 UPB table DO
FOR v TO 2 UPB table DO
### Consider the optimal solution, and consider the "last item" added
to the sack. Removing this item must produce an optimal solution
to the subproblem with the sack"s weight and volume reduced by that
of the item. So we search through all possible "last items": ###
FOR item index TO UPB items DO
BOUNTY item := items[item index];
# Only consider items that would fit: #
IF w >= weight OF item AND v >= volume OF item THEN
# Optimal solution to subproblem + value of item: #
INT candidate := table[w-weight OF item,v-volume OF item] + value OF item;
IF candidate > table[w,v] THEN
table[w,v] := candidate
FI
FI
OD
OD
OD;
[UPB items]INT result; INIT result;
INT w := weight OF sack, v := volume OF sack;
WHILE table[w,v] /= 0 DO
# Find the last item that was added: #
INT needle = table[w,v];
INT item index;
FOR i TO UPB items WHILE
item index := i;
BOUNTY item = items[item index];
INT candidate = table[w-weight OF item WRAP UPB table, v-volume OF item WRAP 2 UPB table] + value OF item;
- WHILE # candidate NE needle DO
SKIP
OD;
# Record it in the result, and remove it: #
result[item index] +:= 1;
w -:= weight OF items[item index];
v -:= volume OF items[item index]
OD;
result
);
[]INT max items = knapsack dp(items, sack); STRUCT (INT value, weight, volume) max := total value(max items, items, sack); max := (value OF max, -weight OF max, -volume OF max);
FORMAT d = $zz-d$;
printf(($"The maximum value achievable (by dynamic programming) is "gl$, value OF max)); printf(($" The number of ("n(UPB items-1)(g", ")g") items to achieve this is: ("n(UPB items-1)(f(d)",")f(d)") respectively"l$,
name OF items, max items));
printf(($" The weight to carry is "f(d)", and the volume used is "f(d)l$,
weight OF max, volume OF max))</lang>Output:
The maximum value achievable (by dynamic programming) is +54500 The number of (panacea, ichor, gold) items to achieve this is: ( 9, 0, 11) respectively The weight to carry is 247, and the volume used is 247
C
<lang c>#include <stdio.h>
double min(double a, double b) {
return a < b ? a : b;
}
struct Bounty {
int value; double weight, volume;
};
struct Bounty panacea = {3000, 0.3, 0.025},
ichor = {1800, 0.2, 0.015},
gold = {2500, 2.0, 0.002},
sack = { 0, 25.0, 0.25 },
current, best;
- define CALC(V) current.V = npanacea * panacea.V + nichor * ichor.V + ngold * gold.V
int main(void) {
int npanacea, nichor, ngold, max_panacea, max_ichor, max_gold; int best_amounts[3]; best.value = 0; max_panacea = (int)min(sack.weight / panacea.weight, sack.volume / panacea.volume); max_ichor = (int)min(sack.weight / ichor.weight, sack.volume / ichor.volume); max_gold = (int)min(sack.weight / gold.weight, sack.volume / gold.volume);
for (npanacea = 0; npanacea <= max_panacea; npanacea++) {
for (nichor = 0; nichor <= max_ichor; nichor++) {
for (ngold = 0; ngold <= max_gold; ngold++) {
CALC(value);
CALC(weight);
CALC(volume);
if (current.value > best.value && current.weight <= sack.weight &&
current.volume <= sack.volume) {
best.value = current.value;
best.weight = current.weight;
best.volume = current.volume;
best_amounts[0] = npanacea;
best_amounts[1] = nichor;
best_amounts[2] = ngold;
}
}
}
}
printf("Maximum value achievable is %d\n", best.value);
printf("This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold\n",
best_amounts[0], best_amounts[1], best_amounts[2]);
printf("The weight to carry is %4.1f and the volume used is %5.3f\n", best.weight, best.volume);
return 0;
}</lang>
Clojure
<lang lisp>(defstruct item :value :weight :volume)
(defn total [key items quantities]
(reduce + (map * quantities (map key items))))
(defn max-count [item max-weight max-volume]
(let [mcw (/ max-weight (:weight item))
mcv (/ max-volume (:volume item))]
(min mcw mcv)))</lang>
We have an item struct to contain the data for both contents and the knapsack. The total function returns the sum of a particular attribute across all items times their quantities. Finally, the max-count function returns the most of that item that could fit given the constraints (used as the upper bound on the combination). Now the real work: <lang lisp>(defn knapsacks []
(let [pan (struct item 3000 0.3 0.025)
ich (struct item 1800 0.2 0.015)
gol (struct item 2500 2.0 0.002)
types [pan ich gol]
max-w 25.0
max-v 0.25
iters #(range (inc (max-count % max-w max-v)))]
(filter (complement nil?)
(pmap
#(let [[p i g] %
w (total :weight types %)
v (total :volume types %)]
(if (and (<= w max-w) (<= v max-v))
(with-meta (struct item (total :value types %) w v) {:p p :i i :g g})))
(for [p (iters pan)
i (iters ich)
g (iters gol)]
[p i g])))))</lang>
The knapsacks function returns a lazy sequence of all valid knapsacks, with the particular content quantities as metadata. The work of realizing each knapsack is done in parallel via the pmap function. The following then finds the best by value, and prints the result. <lang lisp>(defn best-by-value [ks]
(reduce #(if (> (:value %1) (:value %2)) %1 %2) ks))
(defn print-knapsack[k]
(let [ {val :value w :weight v :volume} k
{p :p i :i g :g} ^k]
(println "Maximum value:" (float val))
(println "Total weight: " (float w))
(println "Total volume: " (float v))
(println "Containing: " p "Panacea," i "Ichor," g "Gold")))</lang>
Calling (print-knapsack (best-by-value (knapsacks))) would result in something like:
Maximum value: 54500 Total weight: 24.7 Total volume: 0.247 Containing: 9 Panacea, 0 Ichor, 11 Gold
Further, we could find all "best" knapsacks rather simply (albeit at the cost of some efficiency): <lang lisp>(defn all-best-by-value [ks]
(let [b (best-by-value ks)] (filter #(= (:value b) (:value %)) ks)))
(defn print-knapsacks [ks]
(doseq [k ks] (print-knapsack k) (println)))</lang>
Calling (print-knapsacks (all-best-by-value (knapsacks))) would result in something like:
Maximum value: 54500.0 Total weight: 25.0 Total volume: 0.247 Containing: 0 Panacea, 15 Ichor, 11 Gold Maximum value: 54500.0 Total weight: 24.9 Total volume: 0.247 Containing: 3 Panacea, 10 Ichor, 11 Gold Maximum value: 54500.0 Total weight: 24.8 Total volume: 0.247 Containing: 6 Panacea, 5 Ichor, 11 Gold Maximum value: 54500.0 Total weight: 24.7 Total volume: 0.247 Containing: 9 Panacea, 0 Ichor, 11 Gold
Common Lisp
A dynamic programming O(maxVolume × maxWeight × nItems) solution, where volumes and weights are integral values.
<lang lisp>(defun fill-knapsack (items max-volume max-weight)
"Items is a list of lists of the form (name value weight volume) where weight
and value are integers. max-volume and max-weight, also integers, are the maximum volume and weight of the knapsack. fill-knapsack returns a list of the form (total-value inventory total-volume total-weight) where total-value is the total-value of a knapsack packed with inventory (a list whose elements are elements of items), and total-weight and total-volume are the total weights and volumes of the inventory."
;; maxes is a table indexed by volume and weight, where maxes[volume,weight]
;; is a list of the form (value inventory used-volume used-weight) where
;; inventory is a list of items of maximum value fitting within volume and
;; weight, value is the maximum value, and used-volume/used-weight are the
;; actual volume/weight of the inventory.
(let* ((VV (1+ max-volume))
(WW (1+ max-weight))
(maxes (make-array (list VV WW))))
;; fill in the base cases where volume or weight is 0
(dotimes (v VV) (setf (aref maxes v 0) (list 0 '() 0 0)))
(dotimes (w WW) (setf (aref maxes 0 w) (list 0 '() 0 0)))
;; populate the rest of the table. The best value for a volume/weight
;; combination is the best way of adding an item to any of the inventories
;; from [volume-1,weight], [volume,weight-1], or [volume-1,weight-1], or the
;; best of these, if no items can be added.
(do ((v 1 (1+ v))) ((= v VV) (aref maxes max-volume max-weight))
(do ((w 1 (1+ w))) ((= w WW))
(let ((options (sort (list (aref maxes v (1- w))
(aref maxes (1- v) w)
(aref maxes (1- v) (1- w)))
'> :key 'first)))
(destructuring-bind (b-value b-items b-volume b-weight) (first options)
(dolist (option options)
(destructuring-bind (o-value o-items o-volume o-weight) option
(dolist (item items)
(destructuring-bind (_ i-value i-volume i-weight) item
(declare (ignore _))
(when (and (<= (+ o-volume i-volume) v)
(<= (+ o-weight i-weight) w)
(> (+ o-value i-value) b-value))
(setf b-value (+ o-value i-value)
b-volume (+ o-volume i-volume)
b-weight (+ o-weight i-weight)
b-items (list* item o-items)))))))
(setf (aref maxes v w)
(list b-value b-items b-volume b-weight))))))))</lang>
Use, having multiplied volumes and weights as to be integral:
> (pprint (fill-knapsack '((panacea 3000 3 25)
(ichor 1800 2 15)
(gold 2500 20 2))
250
250))
(54500 ; total-value
((ICHOR 1800 2 15) ; 15 ichor
...
(ICHOR 1800 2 15)
(GOLD 2500 20 2) ; 11 gold
...
(GOLD 2500 20 2))
250 ; total volume
247) ; total weight
E
This is a mostly brute-force general solution (the first author of this example does not know dynamic programming); the only optimization is that when considering the last (third) treasure type, it does not bother filling with anything but the maximum amount.
<lang e>pragma.enable("accumulator")
/** A data type representing a bunch of stuff (or empty space). */ def makeQuantity(value, weight, volume, counts) {
def quantity {
to __printOn(out) {
for name => n in counts { out.print(`$n $name `) }
out.print(`(val=$value wt=$weight vol=$volume)`)
}
to value () { return value }
to weight() { return weight }
to volume() { return volume }
to counts() { return counts }
to subtract(other) { return quantity + other * -1 }
to add(other) {
return makeQuantity(value + other.value (),
weight + other.weight(),
volume + other.volume(),
accum counts for name => n in other.counts() { _.with(name, n+counts.fetch(name, fn {0})) })
}
to multiply(scalar) {
return makeQuantity(value * scalar,
weight * scalar,
volume * scalar,
accum [].asMap() for name => n in counts { _.with(name, n*scalar) })
}
/** a.fit(b) the greatest integer k such that a - b * k does not have negative weight or volume. */
to fit(item) {
return (weight // item.weight()) \
.min(volume // item.volume())
}
}
return quantity
}
/** Fill the space with the treasures, returning candidate results as spaceAvailable - the items. */ def fill(spaceAvailable, treasures) {
if (treasures.size().isZero()) { # nothing to pick
return [spaceAvailable]
}
# Pick one treasure type
def [unit] + otherTreasures := treasures
var results := []
for count in (0..spaceAvailable.fit(unit)).descending() {
results += fill(spaceAvailable - unit * count, otherTreasures)
if (otherTreasures.size().isZero()) {
break # If there are no further kinds, there is no point in taking less than the most
}
}
return results
}
def chooseBest(emptyKnapsack, treasures) {
var maxValue := 0
var best := []
for result in fill(emptyKnapsack, treasures) {
def taken := emptyKnapsack - result # invert the backwards result fill() returns
if (taken.value() > maxValue) {
best := [taken]
maxValue := taken.value()
} else if (taken.value() <=> maxValue) {
best with= taken
}
}
return best
}
def printBest(emptyKnapsack, treasures) {
for taken in chooseBest(emptyKnapsack, treasures) { println(` $taken`) }
}
def panacea := makeQuantity(3000, 0.3, 0.025, ["panacea" => 1]) def ichor := makeQuantity(1800, 0.2, 0.015, ["ichor" => 1]) def gold := makeQuantity(2500, 2.0, 0.002, ["gold" => 1]) def emptyKnapsack \
:= makeQuantity( 0, 25, 0.250, [].asMap())
printBest(emptyKnapsack, [panacea, ichor, gold])</lang>
Forth
<lang forth>\ : value ; immediate
- weight cell+ ;
- volume 2 cells + ;
- number 3 cells + ;
\ item value weight volume number create panacea 30 , 3 , 25 , 0 , create ichor 18 , 2 , 15 , 0 , create gold 25 , 20 , 2 , 0 , create sack 0 , 250 , 250 ,
- fits? ( item -- ? )
dup weight @ sack weight @ > if drop false exit then
volume @ sack volume @ > 0= ;
- add ( item -- )
dup @ sack +! dup weight @ negate sack weight +! dup volume @ negate sack volume +! 1 swap number +! ;
- take ( item -- )
dup @ negate sack +! dup weight @ sack weight +! dup volume @ sack volume +! -1 swap number +! ;
variable max-value variable max-pan variable max-ich variable max-au
- .solution
cr max-pan @ . ." Panaceas, " max-ich @ . ." Ichors, and " max-au @ . ." Gold for a total value of " max-value @ 100 * . ;
- check
sack @ max-value @ <= if exit then sack @ max-value ! panacea number @ max-pan ! ichor number @ max-ich ! gold number @ max-au ! ( .solution ) ; \ and change <= to < to see all solutions
- solve-gold
gold fits? if gold add recurse gold take else check then ;
- solve-ichor
ichor fits? if ichor add recurse ichor take then solve-gold ;
- solve-panacea
panacea fits? if panacea add recurse panacea take then solve-ichor ;
solve-panacea .solution</lang> Or like this... <lang forth>0 VALUE vials 0 VALUE ampules 0 VALUE bars 0 VALUE bag
- 250 3 / #250 #25 / MIN 1+ CONSTANT maxvials
- 250 2/ #250 #15 / MIN 1+ CONSTANT maxampules
- 250 #20 / #250 2/ MIN 1+ CONSTANT maxbars
- RESULTS ( v a b -- k )
3DUP #20 * SWAP 2* + SWAP 3 * + #250 > IF 3DROP -1 EXIT ENDIF 3DUP 2* SWAP #15 * + SWAP #25 * + #250 > IF 3DROP -1 EXIT ENDIF #2500 * SWAP #1800 * + SWAP #3000 * + ;
- .SOLUTION ( -- )
CR ." The traveller's knapsack contains " vials DEC. ." vials of panacea, " ampules DEC. ." ampules of ichor, " CR bars DEC. ." bars of gold, a total value of " vials ampules bars RESULTS 0DEC.R ." ." ;
- KNAPSACK ( -- )
-1 TO bag maxvials 0 ?DO maxampules 0 ?DO maxbars 0 ?DO
K J I RESULTS DUP
bag > IF TO bag K TO vials J TO ampules I TO bars ELSE DROP ENDIF LOOP LOOP LOOP .SOLUTION ;</lang> With the result...
FORTH> knapsack The traveller's knapsack contains 0 vials of panacea, 15 ampules of ichor, 11 bars of gold, a total value of 54500. ok
Fortran
A straight forward 'brute force' approach <lang fortran>PROGRAM KNAPSACK
IMPLICIT NONE REAL :: totalWeight, totalVolume INTEGER :: maxPanacea, maxIchor, maxGold, maxValue = 0 INTEGER :: i, j, k INTEGER :: n(3)
TYPE Bounty INTEGER :: value REAL :: weight REAL :: volume END TYPE Bounty
TYPE(Bounty) :: panacea, ichor, gold, sack, current
panacea = Bounty(3000, 0.3, 0.025) ichor = Bounty(1800, 0.2, 0.015) gold = Bounty(2500, 2.0, 0.002) sack = Bounty(0, 25.0, 0.25)
maxPanacea = MIN(sack%weight / panacea%weight, sack%volume / panacea%volume)
maxIchor = MIN(sack%weight / ichor%weight, sack%volume / ichor%volume)
maxGold = MIN(sack%weight / gold%weight, sack%volume / gold%volume)
DO i = 0, maxPanacea
DO j = 0, maxIchor
Do k = 0, maxGold
current%value = k * gold%value + j * ichor%value + i * panacea%value
current%weight = k * gold%weight + j * ichor%weight + i * panacea%weight
current%volume = k * gold%volume + j * ichor%volume + i * panacea%volume
IF (current%weight > sack%weight .OR. current%volume > sack%volume) CYCLE
IF (current%value > maxValue) THEN
maxValue = current%value
totalWeight = current%weight
totalVolume = current%volume
n(1) = i ; n(2) = j ; n(3) = k
END IF
END DO
END DO
END DO
WRITE(*, "(A,I0)") "Maximum value achievable is ", maxValue WRITE(*, "(3(A,I0),A)") "This is achieved by carrying ", n(1), " panacea, ", n(2), " ichor and ", n(3), " gold items" WRITE(*, "(A,F4.1,A,F5.3)") "The weight to carry is ", totalWeight, " and the volume used is ", totalVolume
END PROGRAM KNAPSACK</lang> Sample output
Maximum value achievable is 54500 This is achieved by carrying 0 panacea, 15 ichor and 11 gold items The weight to carry is 25.0 and the volume used is 0.247
Haskell
This is a brute-force solution: it generates a list of every legal combination of items (options) and then finds the option of greatest value.
<lang haskell>import Data.List (maximumBy) import Data.Ord (comparing)
(maxWgt, maxVol) = (25, 0.25) items =
[Bounty "panacea" 3000 0.3 0.025, Bounty "ichor" 1800 0.2 0.015, Bounty "gold" 2500 2.0 0.002]
data Bounty = Bounty
{itemName :: String,
itemVal :: Int,
itemWgt, itemVol :: Double}
names = map itemName items vals = map itemVal items wgts = map itemWgt items vols = map itemVol items
dotProduct :: (Num a, Integral b) => [a] -> [b] -> a dotProduct factors = sum . zipWith (*) factors . map fromIntegral
options :: Int options = filter fits $ mapM f items
where f (Bounty _ _ w v) = [0 .. m]
where m = floor $ min (maxWgt / w) (maxVol / v)
fits opt = dotProduct wgts opt <= maxWgt &&
dotProduct vols opt <= maxVol
showOpt :: [Int] -> String showOpt opt = concat (zipWith showItem names opt) ++
"total weight: " ++ show (dotProduct wgts opt) ++ "\ntotal volume: " ++ show (dotProduct vols opt) ++ "\ntotal value: " ++ show (dotProduct vals opt) ++ "\n" where showItem name num = name ++ ": " ++ show num ++ "\n"
main = putStr $ showOpt $ best options
where best = maximumBy $ comparing $ dotProduct vals</lang>
Output:
panacea: 9 ichor: 0 gold: 11 total weight: 24.7 total volume: 0.247 total value: 54500
J
Brute force solution. <lang j>mwv=: 25 0.25 prods=: <;. _1 ' panacea: ichor: gold:' hdrs=: <;. _1 ' weight: volume: value:' vls=: 3000 1800 2500 ws=: 0.3 0.2 2.0 vs=: 0.025 0.015 0.002
ip=: +/ .* prtscr=: (1!:2)&2
KS=: 3 : 0
os=. (#:i.@(*/)) mwv >:@<.@<./@:% ws,:vs
bo=.os#~(ws,:vs) mwv&(*./@:>)@ip"_ 1 os
mo=.bo{~{.\: vls ip"1 bo
prtscr &.> prods ([,' ',":@])&.>mo
prtscr &.> hdrs ('total '&,@[,' ',":@])&.> mo ip"1 ws,vs,:vls
LF
)</lang> Example output:
KS'' panacea: 3 ichor: 10 gold: 11 total weight: 24.9 total volume: 0.247 total value: 54500
JavaScript
Brute force.
<lang javascript>var panacea = { 'value': 3000, 'weight': 0.3, 'volume': 0.025 }; var ichor = { 'value': 1800, 'weight': 0.2, 'volume': 0.015 }; var gold = { 'value': 2500, 'weight': 2.0, 'volume': 0.002 };
var knapsack = {'weight': 25, 'volume': 0.25}
for each (var item in [panacea, ichor, gold])
item.max = Math.min(
Math.floor(knapsack.weight / item.weight),
Math.floor(knapsack.volume / item.volume)
);
var max_val = 0; var solutions = [];
for (var g = 0; g <= gold.max; g++) {
for (var p = 0; p <= panacea.max; p++) {
for (var i = 0; i <= ichor.max; i++) {
if (i*ichor.weight + g*gold.weight + p*panacea.weight > knapsack.weight)
continue;
if (i*ichor.volume + g*gold.volume + p*panacea.volume > knapsack.volume)
continue;
var val = i*ichor.value + g*gold.value + p*panacea.value;
if (val > max_val) {
max_val = val;
solutions = [ [g,p,i] ];
}
else if (val == max_val)
solutions.push([g,p,i]);
}
}
}
print("maximum value: " + max_val); for each (var soln in solutions)
print("(gold: " + soln[0] + ", panacea: " + soln[1] + ", ichor: " + soln[2] + ")");</lang>
output:
maximum value: 54500 (gold: 11, panacea: 0, ichor: 15) (gold: 11, panacea: 3, ichor: 10) (gold: 11, panacea: 6, ichor: 5) (gold: 11, panacea: 9, ichor: 0)
M4
A brute force solution: <lang M4>divert(-1) define(`set2d',`define(`$1[$2][$3]',`$4')') define(`get2d',`defn(`$1[$2][$3]')') define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`min',
`define(`ma',eval($1))`'define(`mb',eval($2))`'ifelse(eval(ma<mb),1,ma,mb)')
define(`setv',
`set2d($1,$2,1,$3)`'set2d($1,$2,2,$4)`'set2d($1,$2,3,$5)`'set2d($1,$2,4,$6)')
dnl name,value (each),weight,volume setv(a,0,`knapsack',0,250,250) setv(a,1,`panacea',3000,3,25) setv(a,2,`ichor',1800,2,15) setv(a,3,`gold',2500,20,2)
define(`mv',0) for(`x',0,min(get2d(a,0,3)/get2d(a,1,3),get2d(a,0,4)/get2d(a,1,4)),
`for(`y',0,min((get2d(a,0,3)-x*get2d(a,1,3))/get2d(a,2,3),
(get2d(a,0,4)-x*get2d(a,1,4))/get2d(a,2,4)),
`
define(`z',min((get2d(a,0,3)-x*get2d(a,1,3)-y*get2d(a,2,3))/get2d(a,3,3),
(get2d(a,0,4)-x*get2d(a,1,4)-y*get2d(a,2,4))/get2d(a,3,4)))
define(`cv',eval(x*get2d(a,1,2)+y*get2d(a,2,2)+z*get2d(a,3,2))) ifelse(eval(cv>mv),1,
`define(`mv',cv)`'define(`best',(x,y,z))',
`ifelse(cv,mv,`define(`best',best (x,y,z))')')
')')
divert mv best</lang>
Output:
54500 (0,15,11) (3,10,11) (6,5,11) (9,0,11)
Mathematica
Brute force algorithm: <lang Mathematica>{pva,pwe,pvo}={3000,3/10,1/40}; {iva,iwe,ivo}={1800,2/10,3/200}; {gva,gwe,gvo}={2500,2,2/1000}; wemax=25; vomax=1/4; {pmax,imax,gmax}=Floor/@{Min[vomax/pvo,wemax/pwe],Min[vomax/ivo,wemax/iwe],Min[vomax/gvo,wemax/gwe]};
data=Flatten[Table[{{p,i,g}.{pva,iva,gva},{p,i,g}.{pwe,iwe,gwe},{p,i,g}.{pvo,ivo,gvo},{p,i,g}},{p,0,pmax},{i,0,imax},{g,0,gmax}],2]; data=Select[data,#2<=25&<=1/4&]; First[SplitBy[Sort[data,First[#1]>First[#2]&],First]]</lang> gives back an array of the best solution(s), with each element being value, weight, volume, {number of vials, number of ampules, number of bars}: <lang Mathematica>{{54500,247/10,247/1000,{9,0,11}},{54500,124/5,247/1000,{6,5,11}},{54500,249/10,247/1000,{3,10,11}},{54500,25,247/1000,{0,15,11}}}</lang> if we call the three items by there first letters the best packings are: <lang Mathematica>p:9 i:0 v:11 p:6 i:5 v:11 p:3 i:10 v:11 p:0 i:15 v:11</lang> The volume for all of those is the same, the 'best' solution would be the one that has the least weight: that would the first solution.
Modula-3
Note that unlike Fortran and C, Modula-3 does not do any hidden casting, which is why FLOAT and FLOOR are used. <lang modula3>MODULE Knapsack EXPORTS Main;
FROM IO IMPORT Put; FROM Fmt IMPORT Int, Real;
TYPE Bounty = RECORD
value: INTEGER; weight, volume: REAL;
END;
VAR totalWeight, totalVolume: REAL;
maxPanacea, maxIchor, maxGold, maxValue: INTEGER := 0; n: ARRAY [1..3] OF INTEGER; panacea, ichor, gold, sack, current: Bounty;
BEGIN
panacea := Bounty{3000, 0.3, 0.025};
ichor := Bounty{1800, 0.2, 0.015};
gold := Bounty{2500, 2.0, 0.002};
sack := Bounty{0, 25.0, 0.25};
maxPanacea := FLOOR(MIN(sack.weight / panacea.weight, sack.volume / panacea.volume)); maxIchor := FLOOR(MIN(sack.weight / ichor.weight, sack.volume / ichor.volume)); maxGold := FLOOR(MIN(sack.weight / gold.weight, sack.volume / gold.volume));
FOR i := 0 TO maxPanacea DO
FOR j := 0 TO maxIchor DO
FOR k := 0 TO maxGold DO
current.value := k * gold.value + j * ichor.value + i * panacea.value;
current.weight := FLOAT(k) * gold.weight + FLOAT(j) * ichor.weight + FLOAT(i) * panacea.weight;
current.volume := FLOAT(k) * gold.volume + FLOAT(j) * ichor.volume + FLOAT(i) * panacea.volume;
IF current.weight > sack.weight OR current.volume > sack.volume THEN
EXIT;
END;
IF current.value > maxValue THEN
maxValue := current.value;
totalWeight := current.weight;
totalVolume := current.volume;
n[1] := i; n[2] := j; n[3] := k;
END;
END;
END;
END;
Put("Maximum value achievable is " & Int(maxValue) & "\n");
Put("This is achieved by carrying " & Int(n[1]) & " panacea, " & Int(n[2]) & " ichor and " & Int(n[3]) & " gold items\n");
Put("The weight of this carry is " & Real(totalWeight) & " and the volume used is " & Real(totalVolume) & "\n");
END Knapsack.</lang>
Output:
Maximum value achievable is 54500 This is achieved by carrying 0 panacea, 15 ichor and 11 gold items The weight of this carry is 25 and the volume used is 0.247
OCaml
This is a brute-force solution: it generates a list of every legal combination of items and then finds the best results:
<lang ocaml>type bounty = { name:string; value:int; weight:float; volume:float }
let bounty n d w v = { name = n; value = d; weight = w; volume = v }
let items =
[ bounty "panacea" 3000 0.3 0.025; bounty "ichor" 1800 0.2 0.015; bounty "gold" 2500 2.0 0.002; ]
let max_wgt = 25.0 and max_vol = 0.25
let itmax =
let f it =
let rec aux n =
if float n *. it.weight >= max_wgt
|| float n *. it.volume >= max_vol
then (n)
else aux (succ n)
in
aux 0
in
List.map f items
let mklist n m =
let rec aux i acc = if i > m then (List.rev acc) else aux (succ i) (i::acc) in aux n []
let comb_items = List.map (mklist 0) itmax
let combs ll =
let rec aux acc = function
| [] -> (List.map List.rev acc)
| hd::tl ->
let acc =
List.concat
(List.map
(fun l ->
List.map (fun v -> (v::l)) hd
) acc
)
in
aux acc tl
in
aux [[]] ll
let possibles = combs comb_items
let packs =
let f l =
let g (v, wgt, vol) n it =
(v + n * it.value,
wgt +. float n *. it.weight,
vol +. float n *. it.volume)
in
List.fold_left2 g (0, 0.0, 0.0) l items
in
List.map f possibles
let packs = List.combine packs possibles
let results =
let f (_, wgt, vol) = (wgt <= max_wgt && vol <= max_vol) in List.filter (fun v -> f(fst v)) packs
let best_results =
let max_value = List.fold_left (fun v1 ((v2,_,_),_) -> max v1 v2) 0 results in List.filter (fun ((v,_,_),_) -> v = max_value) results
let items_name =
let f it = it.name in List.map f items
let print ((v, wgt, vol), ns) =
Printf.printf "\ Maximum value: %d \n \ Total weight: %f \n \ Total volume: %f \n \ Containing: " v wgt vol; let f n name = string_of_int n ^ " " ^ name in let ss = List.map2 f ns items_name in print_endline(String.concat ", " ss); print_newline()
let () = List.iter print best_results</lang>
outputs:
Maximum value: 54500 Total weight: 24.700000 Total volume: 0.247000 Containing: 9 panacea, 0 ichor, 11 gold Maximum value: 54500 Total weight: 24.800000 Total volume: 0.247000 Containing: 6 panacea, 5 ichor, 11 gold Maximum value: 54500 Total weight: 24.900000 Total volume: 0.247000 Containing: 3 panacea, 10 ichor, 11 gold Maximum value: 54500 Total weight: 25.000000 Total volume: 0.247000 Containing: 0 panacea, 15 ichor, 11 gold
PARI/GP
Simple brute-force solution, though it avoids the last loop and recalculating values. <lang parigp>best=0; for(a=0,10,
w1=250-3*a;
v1=250-25*a;
for(b=0,16,
w=w1-2*b;
v=v1-15*b;
if(v>=0&&w>=0,
c=min(w\20,v\2);
value=3000*a+1800*b+2500*c;
if(value>=best,
best=value;
print("$"best": "a" panecea, "b" ichor, "c" gold")
)
)
)
)</lang>
Python
Simple Solution
<lang python>class Bounty:
def __init__(self, value, weight, volume):
self.value, self.weight, self.volume = value, weight, volume
panacea = Bounty(3000, 0.3, 0.025) ichor = Bounty(1800, 0.2, 0.015) gold = Bounty(2500, 2.0, 0.002) sack = Bounty( 0, 25.0, 0.25) best = Bounty( 0, 0, 0) current = Bounty( 0, 0, 0)
best_amounts = (0, 0, 0)
max_panacea = int(min(sack.weight // panacea.weight, sack.volume // panacea.volume)) max_ichor = int(min(sack.weight // ichor.weight, sack.volume // ichor.volume)) max_gold = int(min(sack.weight // gold.weight, sack.volume // gold.volume))
for npanacea in xrange(max_panacea):
for nichor in xrange(max_ichor):
for ngold in xrange(max_gold):
current.value = npanacea * panacea.value + nichor * ichor.value + ngold * gold.value
current.weight = npanacea * panacea.weight + nichor * ichor.weight + ngold * gold.weight
current.volume = npanacea * panacea.volume + nichor * ichor.volume + ngold * gold.volume
if current.value > best.value and current.weight <= sack.weight and \
current.volume <= sack.volume:
best = Bounty(current.value, current.weight, current.volume)
best_amounts = (npanacea, nichor, ngold)
print "Maximum value achievable is", best.value print "This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold" % \
(best_amounts[0], best_amounts[1], best_amounts[2])
print "The weight to carry is %4.1f and the volume used is %5.3f" % (best.weight, best.volume)</lang>
General Solution
Requires Python V.2.6+ <lang python>from itertools import product, izip from collections import namedtuple
Bounty = namedtuple('Bounty', 'name value weight volume')
sack = Bounty('sack', 0, 25.0, 0.25)
items = [Bounty('panacea', 3000, 0.3, 0.025),
Bounty('ichor', 1800, 0.2, 0.015),
Bounty('gold', 2500, 2.0, 0.002)]
def tot_value(items_count):
"""
Given the count of each item in the sack return -1 if they can't be carried or their total value.
(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
global items, sack
weight = sum(n * item.weight for n, item in izip(items_count, items))
volume = sum(n * item.volume for n, item in izip(items_count, items))
if weight <= sack.weight and volume <= sack.volume:
return sum(n * item.value for n, item in izip(items_count, items)), -weight, -volume
else:
return -1, 0, 0
def knapsack():
global items, sack # find max of any one item max1 = [min(int(sack.weight // item.weight), int(sack.volume // item.volume)) for item in items]
# Try all combinations of bounty items from 0 up to max1 return max(product(*[xrange(n + 1) for n in max1]), key=tot_value)
max_items = knapsack()
maxvalue, max_weight, max_volume = tot_value(max_items)
max_weight = -max_weight
max_volume = -max_volume
print "The maximum value achievable (by exhaustive search) is %g." % maxvalue item_names = ", ".join(item.name for item in items) print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items) print " The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)</lang>
Sample output
The maximum value achievable (by exhaustive search) is 54500 The number of panacea, ichor, gold items to achieve this is: (9, 0, 11), respectively The weight to carry is 24.7, and the volume used is 0.247
General Dynamic Programming solution
A dynamic programming approach using a 2-dimensional table (One dimension for weight and one for volume). Because this approach requires that all weights and volumes be integer, I multiplied the weights and volumes by enough to make them integer. This algorithm takes O(w*v) space and O(w*v*n) time, where w = weight of sack, v = volume of sack, n = number of types of items. To solve this specific problem it's much slower than the brute force solution.
<lang python>from itertools import product, izip from collections import namedtuple
Bounty = namedtuple('Bounty', 'name value weight volume')
- "namedtuple" is only available in Python 2.6+; for earlier versions use this instead:
- class Bounty:
- def __init__(self, name, value, weight, volume):
- self.name = name
- self.value = value
- self.weight = weight
- self.volume = volume
sack = Bounty('sack', 0, 250, 250)
items = [Bounty('panacea', 3000, 3, 25),
Bounty('ichor', 1800, 2, 15),
Bounty('gold', 2500, 20, 2)]
def tot_value(items_count, items, sack):
""" Given the count of each item in the sack return -1 if they can't be carried or their total value.
(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
weight = sum(n * item.weight for n, item in izip(items_count, items))
volume = sum(n * item.volume for n, item in izip(items_count, items))
if weight <= sack.weight and volume <= sack.volume:
return sum(n * item.value for n, item in izip(items_count, items)), -weight, -volume
else:
return -1, 0, 0
def knapsack_dp(items, sack):
""" Solves the Knapsack problem, with two sets of weights, using a dynamic programming approach """ # (weight+1) x (volume+1) table # table[w][v] is the maximum value that can be achieved # with a sack of weight w and volume v. # They all start out as 0 (empty sack) table = [[0] * (sack.volume + 1) for i in xrange(sack.weight + 1)]
for w in xrange(sack.weight + 1):
for v in xrange(sack.volume + 1):
# Consider the optimal solution, and consider the "last item" added
# to the sack. Removing this item must produce an optimal solution
# to the subproblem with the sack's weight and volume reduced by that
# of the item. So we search through all possible "last items":
for item in items:
# Only consider items that would fit:
if w >= item.weight and v >= item.volume:
table[w][v] = max(table[w][v],
# Optimal solution to subproblem + value of item:
table[w - item.weight][v - item.volume] + item.value)
# Backtrack through matrix to re-construct optimum:
result = [0] * len(items)
w = sack.weight
v = sack.volume
while table[w][v]:
# Find the last item that was added:
aux = [table[w-item.weight][v-item.volume] + item.value for item in items]
i = aux.index(table[w][v])
# Record it in the result, and remove it:
result[i] += 1
w -= items[i].weight
v -= items[i].volume
return result
max_items = knapsack_dp(items, sack)
max_value, max_weight, max_volume = tot_value(max_items, items, sack)
max_weight = -max_weight
max_volume = -max_volume
print "The maximum value achievable (by exhaustive search) is %g." % max_value item_names = ", ".join(item.name for item in items) print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items) print " The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)</lang>
Sample output
The maximum value achievable (by dynamic programming) is 54500 The number of panacea,ichor,gold items to achieve this is: [9, 0, 11], respectively The weight to carry is 247, and the volume used is 247
R
Brute force method <lang r># Define consts weights <- c(panacea=0.3, ichor=0.2, gold=2.0) volumes <- c(panacea=0.025, ichor=0.015, gold=0.002) values <- c(panacea=3000, ichor=1800, gold=2500) sack.weight <- 25 sack.volume <- 0.25 max.items <- floor(pmin(sack.weight/weights, sack.volume/volumes))
- Some utility functions
getTotalValue <- function(n) sum(n*values) getTotalWeight <- function(n) sum(n*weights) getTotalVolume <- function(n) sum(n*volumes) willFitInSack <- function(n) getTotalWeight(n) <= sack.weight && getTotalVolume(n) <= sack.volume
- Find all possible combination, then eliminate those that won't fit in the sack
knapsack <- expand.grid(lapply(max.items, function(n) seq.int(0, n))) ok <- apply(knapsack, 1, willFitInSack) knapok <- knapsack[ok,]
- Find the solutions with the highest value
vals <- apply(knapok, 1, getTotalValue) knapok[vals == max(vals),]</lang>
panacea ichor gold 2067 9 0 11 2119 6 5 11 2171 3 10 11 2223 0 15 11
Ruby
Brute force method,
<lang ruby>KnapsackItem = Struct.new(:volume, :weight, :value) panacea = KnapsackItem.new(0.025, 0.3, 3000) ichor = KnapsackItem.new(0.015, 0.2, 1800) gold = KnapsackItem.new(0.002, 2.0, 2500) maximum = KnapsackItem.new(0.25, 25, 0)
max_items = {} for item in [panacea, ichor, gold]
max_items[item] = [(maximum.volume/item.volume).to_i, (maximum.weight/item.weight).to_i].min
end
maxval = 0 solutions = []
0.upto(max_items[ichor]) do |i|
0.upto(max_items[panacea]) do |p|
0.upto(max_items[gold]) do |g|
next if i*ichor.weight + p*panacea.weight + g*gold.weight > maximum.weight
next if i*ichor.volume + p*panacea.volume + g*gold.volume > maximum.volume
val = i*ichor.value + p*panacea.value + g*gold.value
if val > maxval
maxval = val
solutions = i, p, g
elsif val == maxval
solutions << [i, p, g]
end
end
end
end
puts "The maximal solution has value #{maxval}" solutions.each do |i, p, g|
printf " ichor=%2d, panacea=%2d, gold=%2d -- weight:%.1f, volume=%.3f\n", i, p, g, i*ichor.weight + p*panacea.weight + g*gold.weight, i*ichor.volume + p*panacea.volume + g*gold.volume
end</lang>
The maximal solution has value 54500 ichor= 0, panacea= 9, gold=11 -- weight:24.7, volume=0.247 ichor= 5, panacea= 6, gold=11 -- weight:24.8, volume=0.247 ichor=10, panacea= 3, gold=11 -- weight:24.9, volume=0.247 ichor=15, panacea= 0, gold=11 -- weight:25.0, volume=0.247
Tcl
The following code uses brute force, but that's tolerable as long as it takes just a split second to find all 4 solutions. The use of arrays makes the quote quite legible: <lang Tcl>#!/usr/bin/env tclsh proc main argv {
array set value {panacea 3000 ichor 1800 gold 2500}
array set weight {panacea 0.3 ichor 0.2 gold 2.0 max 25}
array set volume {panacea 0.025 ichor 0.015 gold 0.002 max 0.25}
foreach i {panacea ichor gold} {
set max($i) [expr {min(int($volume(max)/$volume($i)),
int($weight(max)/$weight($i)))}]
}
set maxval 0
for {set i 0} {$i < $max(ichor)} {incr i} {
for {set p 0} {$p < $max(panacea)} {incr p} {
for {set g 0} {$g < $max(gold)} {incr g} {
if {$i*$weight(ichor) + $p*$weight(panacea) + $g*$weight(gold)
> $weight(max)} continue
if {$i*$volume(ichor) + $p*$volume(panacea) + $g*$volume(gold)
> $volume(max)} continue
set val [expr {$i*$value(ichor)+$p*$value(panacea)+$g*$value(gold)}]
if {$val == $maxval} {
lappend best [list i $i p $p g $g]
} elseif {$val > $maxval} {
set maxval $val
set best [list [list i $i p $p g $g]]
}
}
}
}
puts "maxval: $maxval, best: $best"
} main $argv</lang>
$ time tclsh85 /Tcl/knapsack.tcl
maxval: 54500, best: {i 0 p 9 g 11} {i 5 p 6 g 11} {i 10 p 3 g 11} {i 15 p 0 g 11}
real 0m0.188s
user 0m0.015s
sys 0m0.015s
Ursala
The algorithm is to enumerate all packings with up to the maximum of each item, filter them by the volume and weight restrictions, partition the remaining packings by value, and search for the maximum value class. <lang Ursala>#import nat
- import flo
vol = iprod/<0.025,0.015,0.002>+ float* val = iprod/<3000.,1800.,2500.>+ float* wgt = iprod/<0.3,0.2,2.0>+ float*
packings = ~&lrlrNCCPCS ~&K0=> iota* <11,17,13>
solutions = fleq$^rS&hl |=&l ^(val,~&)* (fleq\25.+ wgt)*~ (fleq\0.25+ vol)*~ packings
- cast %nmL
human_readable = ~&p/*<'panacea','ichor','gold'> solutions</lang> output:
< <'panacea': 0,'ichor': 15,'gold': 11>, <'panacea': 3,'ichor': 10,'gold': 11>, <'panacea': 6,'ichor': 5,'gold': 11>, <'panacea': 9,'ichor': 0,'gold': 11>>