如何在以下约束条件下调整0-1背包代码[JAVA]

Question

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

我们有一些标记为1到N的盒子。所有盒子的尺寸都相同。现在，我们必须堆叠一些盒子，但要遵循以下约束：

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

这里给出了提示：

1. 此问题类似于背包问题。
2. 问题的参数是整个塔的当前索引和当前负载限制。
3. 对于每个框，您有两个选择：将框包括在堆栈中（如果可能），或跳过框。
4. [当在堆栈中包含一个框时，子问题塔的负载限制将被更新。新的负载限制是两个值中的最小值（必须确定）。

我已经制作了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 = 20;
    int Loads[] = {15, 13, 7, 8, 2};
    int weights[] = {19, 7, 5, 6, 1};
    int index = Loads.length-1;

    for(int i = 0; i <= 100; i++) {
        for(int j = 0; j < 5; j++) {
           knapsackMemo[i][j] = -1;
        }
    }

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

Answer 1

问题澄清（尝试：））

[我不会直接注释您的代码，但我首先会尝试解释约束并给出一些提示（至少我怎么理解它们），以使您更轻松：

C1：一个盒子不能直接放置多个盒子；

这意味着您基本上可以建造一个盒子的塔楼（因此提示使用“ tower”和“ subtower”）可以容纳有限数量的又称“负载”的盒子。

C2：带有较低标签的盒子不要放在具有较高标签的盒子上；

H3：对于每个框，您有两个选择：将框包括在堆栈中（如果可能），或者跳过该框。

这意味着您已订购盒子或可以订购盒子，然后对其进行迭代（按其最大负载订购）。假设您有3个盒子（已经订购）：盒子15的负载为15，盒子2的负载为12，盒子3的负载为10。由于盒子1不能堆叠在盒子2或盒子3上（由于C2），您可以决定将box1包含在塔中或跳过它（不要使用它）。因此，您只需要保留到目前为止到目前为止已将某些箱号添加到某个（部分）解决方案中的列表。

C3：给出了每个盒子的重量和最大负载。一个盒子上所有盒子的总重量不应超过其最大负载。

H4：在堆栈中包括一个框时，子问题塔的负载限制将被更新。新的负载限制是两个值中的最小值（必须确定）。

空塔已经具有最大容量，然后每增加一个盒子就会减少容量。由于每个箱子的负载可能较低，因此，所有其他箱子的最大重量将是塔架的最小承载能力和最高箱子的最大负载。

示例：假设您的当前塔架具有50的静置容量。现在，您增加了一个重量为10的盒子，最大额外负载为25。现在，塔架的静置容量为min(restCapacity - boxWeight, boxMaxLoad)或min(50 - 10, 25) = min(40,25) = 25。

关于您的代码的评论

使用以上信息和您的主要方法，您似乎已经有了有序的包装盒清单。数组weights似乎定义了每个盒子的重量，而Loads（应命名为loads btw）将定义每个盒子可以承受的额外负载。

话虽如此，您不应该向后（即从长度-1到0）进行迭代，而要向前（即从0到长度-1）进行迭代。

此外，您应该重命名参数以避免混淆，并且还将类型信息放在一起。因此，您应该执行knapsack(int costs[], int values[], int capacity, int index)之类的操作而不是knapsack(int[] weights, int[] loads, int capacity, int index)。