The classic algorithm goes like:
for i in items:
for w in possible total weights (downwards):
if w is achievable with maximum value v:
(w + weight[i]) is also achievable with at least value (v + value[i])
The approach here will be a slight variation of that:
for c in classes:
for w in possible total weights (downwards):
if w is achievable with maximum value v:
for i in items of class c:
(w + weight[i]) is also achievable with at least value (v + value[i])
With your code, the changes would be the following:
Perhaps you will want to make a separate list of items for each class. In line with what is currently done, I'd expect
value
andweight
to become lists of lists, and some variable and array named likenumberOfClasses
andnumberOfClassItems
to monitor the lengths of the new lists.
For example, suppose two class 1 items are (w=2,v=3) and (w=3,v=5), and three class 2 items are (w=1,v=1), (w=4,v=1) and (w=1,v=4). Then we will have:
totalNumberOfItems = 5
,
numberOfClasses = 2
,
numberOfClassItems = [2, 3]
,
value = [[3, 5], [1, 1, 4]]
and
weight = [[2, 3], [1, 4, 1]]
.
That is if you index from0
. Indexing from1
as you do will leave unused zeroes or empty lists at the start of each list.The
for (currentItem)
loop will become afor (currentClass)
loop. The arraysoptimum
andsolution
will be indexed bycurrentClass
instead ofcurrentItem
.The value
option2
will in fact be calculated as the best of several options, one per class item:double option2 = Integer.MIN_VALUE; for (currentItem = 1; currentItem <= numberOfClassItems[currentClass]; currentItem++){ if(weight[currentClass][currentItem] <= currentWeightUnit){ option2 = Math.max (option2, value[currentClass][currentItem] + optimum[currentClass - 1][currentWeightUnit - weight[currentClass][currentItem]]); } }
Perhaps the
solution
array should now containint
instead ofboolean
: the number of item of this class which we take, or some sentinel value (0
or-1
) if we takeoption1
and don't use any item of this class.