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

Question

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

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

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

这里给出提示：

这个问题类似于背包问题。
问题的参数是整个塔的当前索引和当前负载限制。
对于每个框，您有两个选择：将框包含在堆栈中（如果可能），或跳过框。
在堆栈中添加一个盒子时，子问题塔的负载限制将被更新。新的负载限制是两个值中的最小值（您必须确定）。
为了解决最初的问题，塔（最初还没有堆叠的箱子）的良好起始负载限制是 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;

这意味着您基本上可以建造一个塔（因此提示使用“塔”和“子塔”），这些箱子可以承载有限的额外重量，也就是 'load'。

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 顺便说一句）将定义每个盒子可以承受的额外负载。

也就是说你不应该向后迭代（即从长度 - 1 到 0）而是向前迭代（即从 0 到长度 - 1）。

此外，您应该重命名参数以避免混淆，并将类型信息放在一起。所以你应该做 knapsack(int[] weights, int[] loads, int capacity, int index).

而不是 knapsack(int costs[], int values[], int capacity, int index)

算法本身基本上就像遍历一棵二叉树：你分支到“添加”或“跳过”，直到你离开框，达到当前容量或超过它（在这种情况下你需要回溯） .然后你计算每一个“添加”步骤，回溯意味着你取消最后一个“添加”——因为这只有在你添加一个新框时才会发生。

代码可能如下所示：

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

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

How do I tweak my 0-1 knapsack code with the following constraints [JAVA]

java

optimization

dynamic-programming

backtracking