java - 如何使用以下约束调整我的 0-1 背包代码 [JAVA]

Question

我需要编写一个程序，根据以下约束找到可以堆叠的盒子的最大数量。

我们有一些标有 1 到 N 的盒子。所有纸箱的尺寸都相同。现在我们必须堆叠一些盒子，但要受到以下限制:

1. 一个人不能将多个盒子直接放在 table 上；
2. 不得将载重标签较低的箱子放置在载重较高的箱子上；
3. 给出了每个箱子的重量和最大负载。一个箱子上所有箱子的总重量不应超过其最大装载量。

这里给出提示:

1. 这个问题与背包问题类似。
2. 问题的参数是整个塔的当前指数和当前负载限制。
3. 对于每个框，您有两种选择:将框包含在堆栈中(如果可能)，或跳过框。
4. 当在堆栈中添加一个盒子时，子问题塔的负载限制将被更新。新的负载限制是两个值中的最小值(您必须确定)。
5. 为了解决最初的问题，塔的最佳起始负载限制(最初还没有堆叠箱子)为 6000(因为输入中给出的箱子的最大重量为 3000)。

我已经制作了一个 0-1 背包代码，但鉴于上面的提示，我不知道如何调整它。

public static int knapsack(int costs[], int values[], int capacity, int index) {
        if(capacity =z= 0) {
          return 0;
        }
        if(index == 0) {
          if(capacity >= costs[0]) {
            return values[0];
          }
          return 0;
        }
        if(knapsackMemo[capacity][index] != -1) {
          return knapsackMemo[capacity][index];
        }
        //Choice 1: If added to knapsack
        int choice1 = -1;
        if(capacity >= costs[index]) {
          choice1 = knapsack(costs, values, capacity - costs[index], index - 1) + values[index];
        }
        //Choice 2: If not added to knapsack
        int choice2 = knapsack(costs, values, capacity, index - 1);
        knapsackMemo[capacity][index] = Math.max(choice1, choice2);
        return knapsackMemo[capacity][index];
}

这是我的主要方法:

public static void main(String[] args) {
    int budget = 6000;
    int loads[] = {15, 13, 7, 8, 2};
    int weights[] = {19, 7, 5, 6, 1};
    int index = 0;


    System.out.println(knapsack(weights, loads, budget, index));
}

Answer 1

问题澄清(尝试:))

我不会直接评论您的代码，但我会首先尝试解释一下约束和提示(至少是我如何理解它们)，以使您更容易:

C1: One cannot put more than one box directly upon a box;

这意味着您基本上 build 了一座由盒子组成的塔(因此提示使用“塔”和“子塔”)，这些盒子可以承载有限数量的额外重量，即“负载”。

C2: Boxes with lower load labels are not to be put upon one with a higher load;

H3: For each box, you have two choices: either to include the box in the stack (if possible), or skip the box.

这意味着您的盒子已被订购或可以被订购，从而进行迭代(按最大负载对它们进行排序)。假设您有 3 个箱子(已订购):箱子 1 的负载为 15，箱子 2 的负载为 12，箱子 3 的负载为 10。由于箱子 1 不能堆叠在箱子 2 或箱子 3 上(由于 C2)，您可以决定将 box1 包含在塔中或跳过它(并且不要使用它)。因此，您只需保留到目前为止已添加到某个(部分)解决方案中的框编号的列表。

C3: The weight and maximum load for each box are given. The total weight of all boxes upon a box should not exceed its maximum load.

H4: When including a box in the stack, the load limit of the subproblem tower will be updated. The new load limit is the minimum of two values (that you have to determine).

空塔已经有最大容量，随着每个盒子的添加，容量将会减少。由于每个箱子可以具有较低的负载，因此其顶部所有附加箱子的最大重量将是塔的剩余容量和最高箱子的最大负载中的最小值。

示例:假设您当前的塔的剩余容量为 50。您现在添加一个重量为 10 的箱子，最大附加负载为 25。现在塔的剩余容量为 min(restCapacity - boxWeight, boxMaxLoad ) 或 min(50 - 10, 25) = min(40,25) = 25。

对您的代码的评论

根据上面的信息和您的主要方法，您似乎已经有了一个几乎有序的框列表(框 3 和框 4 必须交换)。数组 weights 似乎定义了每个盒子的重量，而 Loads (顺便说一句，应该命名为 loads)将定义每个盒子可以承受的额外负载采取。

也就是说，您不应该向后迭代(即从 length - 1 到 0)，而应该向前迭代(即从 0 到 length - 1)。

此外，您应该重命名参数以避免混淆，并将类型信息放在一起。因此，您应该执行类似 knapsack(int[]weights, int[]loads, intcapacity) 的操作，而不是 knapsack(intcost[], intvalues[], intcapacity, intindex) ，整数索引)。

该算法本身基本上就像遍历二叉树:您分支到“添加”或“跳过”，直到超出框、达到当前容量或超过它(在这种情况下您需要回溯)。然后，您计算所采取的每个“添加”步骤，回溯将意味着您取消最后一个“添加” - 因为只有在添加新框时才会发生这种情况。

代码可能如下所示:

int knapsack(int weights[], int loads[], int capacity, int index) {
  //no more boxes or exactly out of capacity, return 0 additional boxes
  if( index >= weights.length || capacity == 0) {  
    return 0;
  }

  //capacity exceeded, we need to remove the previous box so we return -1
  if( capacity < 0 ) {
    return -1;
  }

  //"add" branch: since we added 1 box we add 1 to the result of the subtree 
  //(which could be -1 if we exceeded the capacity and thus the result would be 0).
  int resultIfAdded = knapsack(weights, loads, 
                              //the rest capacity is the current capacity minus the current box' weight
                              //or the current box' load if it is lower
                              Math.min( capacity - weights[index], loads[index]), 
                              index + 1 ) + 1;

  //"skip" branch, we just increase the index
  int resultIfSkipped = knapsack(weights, loads, capacity, index + 1 );        

  //we want the highest number of boxes we can stack so return the maximum of both branches
  return Math.max( resultIfAdded, resultIfSkipped );
}