从集合中找到产生最小浪费量的数字

Question

该方法接收一个集合和一条杆的长度作为参数。该解决方案应输出从集合中选择哪些数字，如果从杆的长度中移除某些数字，则会产生最小的浪费。例如，当杆长为10，集合包括6、1、4时，解决方案是6和4，浪费量为0。然而我在条件回溯方面遇到了一些问题。我还尝试使用“wastage”全局变量来帮助实现回溯，但没有成功。

SetInt是一个手工制造的集合实现，它可以添加、删除、检查集合是否为空，并返回集合中的最小值。

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package recback;


public class RecBack {

   public static int WASTAGE = 10;

    public static void main(String[] args) {



         int[] nums = {6,1,4};
        //Order Numbers

        int barLength = 10;
        //Bar length

        SetInt possibleOrders = new SetInt(nums.length);
        SetInt solution = new SetInt(nums.length);
        //Set Declarration


        for (int i = 0; i < nums.length; i++)possibleOrders.add(nums[i]);
        //Populate Set

        SetInt result = tryCutting(possibleOrders, solution, barLength);
        result.printNumbers();


    }

    private static SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft)
      {



        SetInt clonedSet = possibleOrders.cloneSet(); //initialise selection of candidates

        for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat
          {

            int a = clonedSet.min(); //select next candidate

            if (a <= lengthleft) //if accecptable
              { 
                solution.add(a); //record candidate
                lengthleft -= a;
                clonedSet.remove(a); //remove from original set

                if (!clonedSet.isEmpty()) //solution not complete
                  {
                    WASTAGE +=a;
                    tryCutting(clonedSet, solution, lengthleft);//try recursive call

                    if (lengthleft > WASTAGE)//if not successfull
                      {
                        WASTAGE += a;
                        solution.remove(a);
                      }

                  } //solution not complete
              }
          } //for loop
        return solution;

      }
  }

- Newb

Answer 1

你有几个问题。

其中一个是这一行代码： int a = clonedSet.min(); //select next candidate

如果你按照你的例子走，它会找到值1并首先使用它，所以1和4会被使用，但6不会。

你最好寻找小于等于剩余长度的最大值。

我也觉得这一行代码很奇怪：

WASTAGE +=a;

我认为你应该进行减法运算，而且为什么要修改静态整数？

如果这是可变的东西，那么你应该只需传入它，然后在完成浪费量时将其传回，因此你需要返回一个新类，包括解决方案和浪费的数量。

对于递归，你需要先看看你的例子，然后逐个步骤地检查它是否符合你的预期行为。

你可能需要看一下这个循环：

for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat

如果您正在递归地执行此操作，那么如果您有3个可能的解决方案，我相信您最终会进行6次测试，而不是按照您的预期进行三次。

如果您删除for循环，应该也没问题。加入一个打印语句，这样您就可以观察每次执行的情况。

更新：

根据更多信息，您需要做的是收集所有可能的解决方案，然后进行第一轮尝试，找到可行的解决方案。然后，将可能的解决方案向左或向右移动，再次尝试。

当您完全移动时，您将尝试各种组合，但并非每种可能的组合，但是您可以将这些解决方案取出，并查看哪个是最优的。

如果您想测试更多的组合，则需要循环删除一个项目，这可能是递归的。

因此，您需要在另一个函数内部使用一个递归函数，以便递归地遍历所有可能的组合，然后递归地寻找问题的解决方案。

我认为寻找max可能是最好的选择，但这只是我的直觉，也可以证明min是最好的选择。

- James Black

---

这里的问题在于它必须回溯，因此如果值未达到最佳结果，则刚刚添加到解决方案中的结果将被再次删除，以便回溯并进行测试。我们被告知可以使用min结果完成它。另外它不应该是静态的，这是我的错误。最后，循环应该测试每个可能的解决方案，因此如果集合是2,6,2,4; 可以找到的解决方案是：6,4和6,2,2我希望这有意义！ - Newb

Answer 2

我同意詹姆斯的观点，您不需要/不想要循环。据我所知，您的“tryCutting”算法接受一个可能订单列表、正在考虑的当前解决方案以及如果您要切割当前解决方案时剩余的长度。然后您需要：

• 从订单中删除最短的切割。如果它比剩余长度长，则不再尝试。否则，
• 第一种情况：您未满足该切割-使用新的订单列表和相同的当前长度再次尝试切割
• 第二种情况：您已经满足了该切割。将其添加到当前解决方案中，并使用新的订单列表和减去该切割的长度来尝试切割。最后再次将其从当前解决方案中移除（用于回溯）
• 将最短的切割放回订单中（用于回溯）

现在，对于您尝试的每种情况，请检查剩余长度是否比迄今为止的全局最佳情况更短。如果是，则使用当前解决方案的克隆更新全局最佳情况。

这将为您提供单个最佳解决方案或其中一个，如果有几个同样好的解决方案。要获取所有解决方案，您需要全局SetInts列表。如果找到比当前更好的解决方案，请清除列表并添加新解决方案。如果它与当前最佳解决方案相等，则只需添加它。

以下是代码：

public static void main(String[] args) {
    int[] nums = {6,1,4};          //Order Numbers
    int barLength = 10;         //Bar length
    bestSolution = new HashSet<SetInt>();
    bestWastage = barLength;
    SetInt possibleOrders = new SetInt(nums.length);
    SetInt solution = new SetInt(nums.length);         //Set Declarration
    for (int i = 0; i < nums.length; i++) {
        possibleOrders.add(nums[i]);         //Populate Set
    }
    tryCutting(possibleOrders, solution, barLength);
    for (SetInt result : bestSolution) {
        result.printNumbers();
    }

}

private static int bestWastage;
private static Set<SetInt> bestSolution;

private static void tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft) {
    if (lengthleft < bestWastage) {
        // Better than the best solution
        bestWastage = lengthleft;
        bestSolution.clear();
        bestSolution.add(solution.cloneSet());
    } else if (lengthleft == bestWastage) {
        // Just as good as the best solution
        bestSolution.add(solution.cloneSet());
    }
    int a = possibleOrders.min(); //select next candidate
    if (a <= lengthleft) { // If acceptable
        possibleOrders.remove(a); // Remove it
        tryCutting(possibleOrders, solution, lengthleft); // Try without that cut
        solution.add(a); // add to the solution
        tryCutting(possibleOrders, solution, lengthleft - a); // Try with that cut
        solution.remove(a); // remove again
        possibleOrders.add(a); // add the candidate back on again
    }
}

- Peter Hull

---

如果您能够完成翻译，我将不胜感激。 - Newb

我自己解决了这个问题，使用了与你类似的方法。我添加了第二个递归调用，但我没有实现哈希集。不过我认为如果我这样做了，它会帮助我存储多个解决方案。谢谢。 - Newb