Modified Backpack Algorithm

Question

I have different classes of items. Each element has valueand weight.

For instance:

ClassA: [A1, A2, A3]

ClassB: [B1, B2, B3]

ClassC: [C1, C2, C3]

How can I change the classic 0-1 Knapsack problem so that the algorithm optimizes a solution that maximizes the overall value, considers all the elements in the class, but allows me to select at most one element from the same 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;
}
}

Thank!

Answer 1

The classic algorithm is as follows:

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 small change:

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

---

In your code, the changes will be as follows:

• , . , , , value weight , numberOfClasses numberOfClassItems .
  /" > , , 1 (w = 2, v = 3) (w = 3, v = 5), 2: (w = 1, v = 1), (w = 4, v = 1) (w = 1, v = 4). :
  totalNumberOfItems = 5,
  numberOfClasses = 2,
  numberOfClassItems = [2, 3],
  value = [[3, 5], [1, 1, 4]]
weight = [[2, 3], [1, 4, 1]].
  , 0. 1, , .

• for (currentItem) for (currentClass). optimum solution currentClass currentItem.

• option2 : : 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]]); } }

• , solution int boolean: , , - (0 -1), option1 - .

Answer 2

, A,B,C , .

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

DP : -

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