11

下面将一个集合传递给此方法，并且还传递了一个条的长度。如果从条长度中删除该集合中的某些数字，则该解决方案应输出该集合中的数字，这些数字给出的浪费最少。所以，条长 10，集合包括 6,1,4，所以解决方案是 6 和 4，浪费是 0。我在通过集合回溯的条件方面遇到了一些问题。我还尝试使用浪费的“全局”变量来帮助回溯方面，但无济于事。

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;

      }
  }
4

2 回答 2

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 次测试，而不是经历 3 次，这是您所期望的。

如果您删除 for 循环，您应该仍然可以。放入打印语句，以便您每次都可以看到它。

更新：

根据更多信息，您要做的是收集所有可能的解决方案，然后您可以做的是通过并进行第一遍，获得以这种方式工作的解决方案。然后，向左或向右移动可能的解决方案，然后再试一次。

当您一直转换时，您将尝试各种组合，但不是所有可能的组合，但是，您可以采用这些解决方案，看看哪个是最佳的。

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

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

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

于 2011-04-15T18:17:04.553 回答
0

我同意詹姆斯的观点，你不需要/想要循环。据我了解，您的“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
    }
}
于 2011-04-21T10:58:59.433 回答