Modified Knapsack algorithm

Question

I've different classes of items. Each item has value and weight.

For example:

ClassA: [A1, A2, A3]

ClassB: [B1, B2, B3]

ClassC: [C1, C2, C3]

How should I modify classic 0-1 Knapsack problem so that algorithm optimize solution maximizing overall value, consider all items in class but allowed to pick at at most one item from one class?

package knapsack;

import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    private int totalNumberOfItems;
    private int maxmimumKnapsackCapacityUnits;

    private double[][] optimum;
    private boolean[][] solution;

    private double [] value;
    private int [] weight;

    public Knapsack(int knapsackCapacityUnits, List<KnapsackItem> items){

        this.totalNumberOfItems = items.size();
        this.maxmimumKnapsackCapacityUnits = knapsackCapacityUnits;

        this.optimum = new double[items.size() + 1][knapsackCapacityUnits + 1];
        this.solution = new boolean[items.size() + 1][knapsackCapacityUnits + 1];

        this.value = new double[items.size() + 1];
        this.weight = new int[items.size() + 1];

        int index=1;
        for(KnapsackItem item : items){
            value[index] = item.value;
            weight[index] = item.weight;
            index++;
        }


}

public List<KnapsackItem> optimize(){

    for(int currentItem = 1; currentItem <= totalNumberOfItems; currentItem++){
        for(int currentWeightUnit = 1; currentWeightUnit <= maxmimumKnapsackCapacityUnits; currentWeightUnit++){

            double option1 = optimum[currentItem - 1][currentWeightUnit];

            double option2 = Integer.MIN_VALUE;

            if(weight[currentItem] <= currentWeightUnit){
                option2 = value[currentItem] + optimum[currentItem-1][currentWeightUnit - weight[currentItem]];
            }

            optimum[currentItem][currentWeightUnit] = Math.max(option1, option2);
            solution[currentItem][currentWeightUnit] = (option2 > option1);
        }
    }

    boolean take [] = new boolean[totalNumberOfItems + 1];
    for(int currentItem = totalNumberOfItems,
            currentWeightUnit = maxmimumKnapsackCapacityUnits; 
            currentItem > 0; currentItem --){
        if(solution[currentItem][currentWeightUnit]){
            take[currentItem] = true;
            currentWeightUnit = currentWeightUnit - weight[currentItem];
        }
        else{
            take[currentItem] = false;
        }
    }

    List<KnapsackItem> items = new ArrayList<KnapsackItem>();
    for(int i = 0; i < take.length; i++){
        KnapsackItem newItem = new KnapsackItem();
        newItem.value = value[i];
        newItem.weight = weight[i];
        newItem.isTaken = take[i];
        items.add(newItem);
    }

    return items;
}
}

Thanks!

Answer 1

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:

1. 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 and weight to become lists of lists, and some variable and array named like numberOfClasses and numberOfClassItems 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 from 0. Indexing from 1 as you do will leave unused zeroes or empty lists at the start of each list.

2. The for (currentItem) loop will become a for (currentClass) loop. The arrays optimum and solution will be indexed by currentClass instead of currentItem.

3. 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]]); } }

4. Perhaps the solution array should now contain int instead of boolean: the number of item of this class which we take, or some sentinel value (0 or -1) if we take option1 and don't use any item of this class.

Answer 2

The approach to solve this problem is to consider classes A,B,C as items themselves and then proceed to make the choices in the individual class to select the best out of them.

number of items = number of classes = N
Knapsack capacity  = W
Let item[i][k] be kth item of ith class.

simple DP solution to problem with simple modification to knapsack solution :-

int DP[n][W+1]={0};

//base condition for item = 0

for(int i=0;i<=W;i++) {

   for(int j=0;j<item[0].size();j++) {
         if(i>=item[0][j].weight) {
              DP[0][i] = max(DP[0][i],item[0][j].value);
         }
   }

} 

//Actual DP 

for(int k=0;k<=W;k++) {

  for(int i=0;i<n;i++) {  

    for(int j=0;j<item[i].size();j++) {
         if(k>=item[i][j].weight) {
              DP[i][k] = max(DP[i][k],DP[i-1][k-item[i][j].weight]+item[i][j].value);
         }
     }

     DP[i][k] = max(DP[i][k],DP[i-1][k]);

  }

}

print("max value : ",DP[n-1][W]);