从一组中查找给出最少量废物的数字

Question

下面将一个集合传递给此方法,并且还会传入一个条形长度.如果从条形长度中移除了集合中的某些数字,则解决方案应输出集合中的数字,这些数字会产生最少量的浪费.因此,条形长度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;

      }
  }

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

如果你删除 for 循环，你应该仍然没问题。放入打印语句，以便您每次都能看到它的执行过程。

更新：

基于更多的信息，你要做的就是收集所有可能的解决方案，然后你能做的就是遍历并执行第一遍，得到可行的解决方案。然后，向左或向右移动可能的解决方案，然后重试。

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

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

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

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