algorithm - 改进的背包算法

Question

我有不同类别的元素。每个项目都有 value 和 weight。

例如:

A 类:[A1，A2，A3]

B 类:[B1、B2、B3]

C 类:[C1、C2、C3]

我应该如何修改经典的 0-1 背包问题，以便算法优化解决方案以最大化整体值(value)，考虑类中的所有项目但允许从一个类中最多选择一个项目？

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

谢谢!

Answer 1

经典算法是这样的:

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

这里的方法会略有不同:

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

---

使用您的代码，更改如下:

1. 也许您会想要为每个类(class)制作一个单独的项目列表。根据目前所做的，我预计 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正如您所做的那样，将在每个列表的开头留下未使用的零或空列表。

2. for (currentItem)循环将变为 for (currentClass)环形。数组 optimum和 solution将由 currentClass 索引而不是 currentItem .

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

4. 也许是 solution数组现在应该包含 int而不是 boolean :我们采用的此类项目的数量，或者如果我们采用 0 的一些标记值( -1 或 option1 )并且不要使用此类的任何项目。