Knapsack problem/Unbounded

Knapsack problem/Unbounded
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:

1. There are four solutions that maximise the value taken. Only one need be given.

ALGOL 68

Translation of: Python

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))

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

Translation of: Fortran

<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;

1. 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;

}</c>

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

Fortran

Works with: Fortran version 90 and later

A straight forward 'brute force' approach

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

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.

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

Output:

panacea: 9
ichor: 0
gold: 11
total weight: 24.7
total volume: 0.247
total value: 54500

Modula-3

Translation of: Fortran

Note that unlike Fortran and C, Modula-3 does not do any hidden casting, which is why FLOAT and FLOOR are used.

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.

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

Python

Simple Basic Solution

This version is easy to understand and gets the job done, not over-generalizing. It's often the first kind of solution to try, and often good enough to keep. It follows the KISS principle, and doesn't use Python features just because they are available. It doesn't even need many comments. <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) </python>

General Solution

Requires Python V.2.6+ <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) </python>

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(wv) space and O(wvn) time, where w = weight of sack, v = volume of sack, n = number of types of items.

<python>from collections import namedtuple

Bounty = namedtuple('Bounty', 'name value weight volume')

1. "namedtuple" is only available in Python 2.6+; for earlier versions use this instead:
2. class Bounty:
3. def __init__(self, name, value, weight, volume):
4. self.name = name
5. self.value = value
6. self.weight = weight
7. self.volume = volume

items = [ Bounty('panacea', 3000, 3, 25),

         Bounty('ichor',   1800,   2,  15),
         Bounty('gold',    2500,  20,   2),
         ]

sack = Bounty('sack', 0, 250, 250)

def totvalue(itemscount, items=items, sack=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 zip(itemscount, items) )
   volume = sum( n*item.volume for n, item in zip(itemscount, items) )
   if weight > sack.weight or volume > sack.volume:
       return -1, 0, 0
   return sum( n*item.value for n, item in zip(itemscount, items) ), -weight, -volume

def knapsack_dp(items = items, sack = 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 range(sack.weight+1) ]
   
   for w in range(0, sack.weight+1):
       for v in range(0, 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] != 0:
       # Find the last item that was added:
       i = [table[w-item.weight][v-item.volume] + item.value
            for item in items].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

maxitems = knapsack_dp() maxvalue, maxweight, maxvolume = totvalue(maxitems) maxweight = -maxweight; maxvolume = -maxvolume

print "The maximum value achievable (by dynamic programming) is %g" % maxvalue print " The number of %s items to achieve this is: %s, respectively" % (

   ','.join(item.name for item in items), maxitems )

print " The weight to carry is %d, and the volume used is %d" % (

   maxweight, maxvolume )</python>

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

Visual Basic

Works with: Visual Basic version 6.0

Option Explicit

Type TreasureType
    Name As String
    Units As String
    Value As Currency
    weight As Single
    Volume As Single
End Type

Type SolutionType
    Desc As String
    Value As Currency
End Type

Type KnapsackType
    Contents() As Integer
    CapacityWeight As Single
    CapacityVolume As Single
End Type

Dim Treasures() As TreasureType

Public Sub Main()
    
    SetupTreasureShangriLa
    Debug.Print CalcKnapsack(25, 0.25)
    
End Sub

Public Sub SetupTreasureShangriLa()

    ReDim Treasures(3) As TreasureType
    With Treasures(1)
        .Name = "panacea"
        .Units = "vials"
        .Value = 3000
        .weight = 0.3
        .Volume = 0.025
    End With
    With Treasures(2)
        .Name = "ichor"
        .Units = "ampules"
        .Value = 1800
        .weight = 0.2
        .Volume = 0.015
    End With
    With Treasures(3)
        .Name = "gold"
        .Units = "bars"
        .Value = 2500
        .weight = 2
        .Volume = 0.002
    End With
    
End Sub

Public Function CalcKnapsack(ByVal sCapacityWeight As Single, ByVal sCapacityVolume As Single) As String
Dim Knapsack As KnapsackType
Dim Solution As SolutionType

    Knapsack.CapacityVolume = sCapacityVolume
    Knapsack.CapacityWeight = sCapacityWeight
    ReDim Knapsack.Contents(UBound(Treasures)) As Integer
    Call Stuff(Knapsack, Solution, 1)
    Debug.Print "Maximum value: " & Solution.Value
    Debug.Print "Ideal Packing(s): " & vbCrLf & Solution.Desc
    
End Function

Private Sub Stuff(ByRef Knapsack As KnapsackType, ByRef Solution As SolutionType, ByVal nDepth As Integer)
Dim nI As Integer
Dim curVal As Currency
Dim sWeightRemaining As Single
Dim sVolumeRemaining As Single
Dim nJ As Integer

    sWeightRemaining = CalcWeightRemaining(Knapsack)
    sVolumeRemaining = CalcvolumeRemaining(Knapsack)

    With Treasures(nDepth)
        If nDepth = UBound(Treasures) Then
            Knapsack.Contents(nDepth) = Min(Fix(sWeightRemaining / .weight), Fix(sVolumeRemaining / .Volume))
            curVal = CalcValue(Knapsack)
            If curVal > Solution.Value Then
                Solution.Value = curVal
                Solution.Desc = BuildDesc(Knapsack)
            ElseIf curVal = Solution.Value Then
                Solution.Desc = Solution.Desc & vbCrLf & "or" & vbCrLf & vbCrLf & BuildDesc(Knapsack)
            End If
        Else
            For nI = 0 To Min(Fix(sWeightRemaining / .weight), Fix(sVolumeRemaining / .Volume))
                Knapsack.Contents(nDepth) = nI
                For nJ = nDepth + 1 To UBound(Treasures)
                    Knapsack.Contents(nJ) = 0
                Next nJ
                Call Stuff(Knapsack, nDepth + 1)
            Next nI
        End If
    End With

End Sub

Private Function CalcValue(ByRef Knapsack As KnapsackType) As Currency
Dim curTmp As Currency
Dim nI As Integer

    For nI = 1 To UBound(Treasures)
        curTmp = curTmp + (Treasures(nI).Value * Knapsack.Contents(nI))
    Next nI
    
    CalcValue = curTmp
    
End Function

Private Function Min(ByVal vA As Variant, ByVal vB As Variant) As Variant

    If vA < vB Then
        Min = vA
    Else
        Min = vB
    End If

End Function

Private Function CalcWeightRemaining(ByRef Knapsack As KnapsackType) As Single
Dim sTmp As Single
Dim nI As Integer

    For nI = 1 To UBound(Treasures)
        sTmp = sTmp + (Treasures(nI).weight * Knapsack.Contents(nI))
    Next nI
    
    CalcWeightRemaining = Knapsack.CapacityWeight - sTmp
    
End Function

Private Function CalcvolumeRemaining(ByRef Knapsack As KnapsackType) As Single
Dim sTmp As Single
Dim nI As Integer

    For nI = 1 To UBound(Treasures)
        sTmp = sTmp + (Treasures(nI).Volume * Knapsack.Contents(nI))
    Next nI
    
    CalcvolumeRemaining = Knapsack.CapacityVolume - sTmp
    
End Function

Private Function BuildDesc(ByRef Knapsack As KnapsackType) As String
Dim cTmp As String
Dim nI As Integer

    For nI = 1 To UBound(Treasures)
        cTmp = cTmp & Knapsack.Contents(nI) & " " & Treasures(nI).Units & " of " & Treasures(nI).Name & vbCrLf
    Next nI
    BuildDesc = cTmp

End Function

Output:

Maximum value: 54500
Ideal Packing(s): 
0 vials of panacea
15 ampules of ichor
11 bars of gold

or

3 vials of panacea
10 ampules of ichor
11 bars of gold

or

6 vials of panacea
5 ampules of ichor
11 bars of gold

or

9 vials of panacea
0 ampules of ichor
11 bars of gold