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

问题描述

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

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

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

这里给出了提示：

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

标签： javaoptimizationdynamic-programmingbacktracking

解决方案

问题澄清（尝试:)）

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

C1：不能在一个盒子上直接放一个以上的盒子；

这意味着您基本上建造了一个塔（因此提示使用“塔”和“子塔”），可以承载有限数量的额外重量，即“负载”。

C2：低负荷标签的箱子不能放在负荷高的箱子上；

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

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

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

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

空塔已经有一个最大容量，然后随着每个盒子的增加而减少。由于每个箱子都可以有较低的负载，因此在其顶部的所有附加箱子的最大重量将是塔架剩余容量的最小值和最高箱子的最大负载。

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

对您的代码的评论

有了上面的信息和你的主要方法，你似乎已经有了一个几乎有序的盒子列表（盒子 3 和 4 必须交换）。该数组weights似乎定义了每个盒子的重量，而Loads（应该命名为loadsbtw）将定义每个盒子可以承受的额外负载。

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

此外，您应该重命名参数以避免混淆，并将类型信息放在一起。因此，knapsack(int costs[], int values[], int capacity, int index)您应该做类似的事情，而不是knapsack(int[] weights, int[] loads, 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 );
}

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

问题描述

解决方案

推荐阅读