Knapsack problem/Unbounded: Difference between revisions
m →{{header|J}}: code rearrangement |
|||
Line 429: | Line 429: | ||
mo=.bo{~{.\: vls ip"1 bo |
mo=.bo{~{.\: vls ip"1 bo |
||
prtscr &.> prods ([,' ',":@])&.>mo |
prtscr &.> prods ([,' ',":@])&.>mo |
||
prtscr &.> hdrs ('total '&,@[,' ',":@])&.> |
prtscr &.> hdrs ('total '&,@[,' ',":@])&.> mo ip"1 ws,vs,:vls |
||
LF |
LF |
||
) |
) |
Revision as of 17:13, 20 January 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
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
<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;
}</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
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
J
Brute force solution.
mxW=: 25 mxV=: 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.@(*/))(mxW,mxV) >:@<.@<./@:% ws,:vs bo=.os#~(ws,:vs) (mxW,mxV)&(*./@:>)@ip"_ 1 os mo=.bo{~{.\: vls ip"1 bo prtscr &.> prods ([,' ',":@])&.>mo prtscr &.> hdrs ('total '&,@[,' ',":@])&.> mo ip"1 ws,vs,:vls LF )
Example output:
KS'' panacea: 3 ichor: 10 gold: 11 total weight: 24.9 total volume: 0.247 total value: 54500
Modula-3
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 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(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.
<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)</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
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