修改后的背包算法

Question

修改后的背包算法

algorithmknapsack-problem

4

我有不同类别的物品。每个物品都有价值和重量。

例如：

ClassA: [A1, A2, A3]

ClassB: [B1, B2, B3]

ClassC: [C1, C2, C3]

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

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

谢谢！

- Wild Goat

2个回答

0

解决这个问题的方法是将类A,B,C视为项目本身，然后在每个类中进行选择，以选择最佳选项。

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

简单的动态规划解决方案，对背包问题的解决方案进行简单修改：

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

- Vikram Bhat

这应该怎么工作？首先，一个类中没有单一的“最佳”项目。例如，一个类可能包含一个重量为3、价值为5的项目，以及另一个重量为5、价值为8的项目。当你有限的容量时，你事先不知道哪个更好。 - Gassa

@Gassa，由于这是一个DP，我们不会提前决定，而是逐个从类别中选择每个项目并检查结果，选择为特定子问题提供最大权重的项目。它类似于原始背包问题，但只考虑一个或零个类别中的项目。您能告诉我您从伪代码中没有理解的内容吗？ - Vikram Bhat

抱歉，我觉得"从类中选择最佳项"这句话有些不清楚：它让我感觉好像"每个类别中都只有一个最佳项"。所以，我没有太在意代码。但现在我看了代码，它似乎做了正确的事情。 - Gassa

@VikramBhat，你对这个有什么想法吗-https://math.stackexchange.com/questions/2415617？谢谢。 - Royi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gassa · Accepted Answer

经典算法如下：

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. 可能您会想为每个类别单独列出物品清单。按照当前的做法，我预计“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. 实际上，选项2的值将计算为多个选项中的最佳选项之一，每个类别项目一个：


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：我们取这个类别的物品数量，或者如果我们采用option1并且不使用此类别的任何物品，则使用某些标记值（0或-1）。