递归回溯问题

Question

大家好，最近发布了关于我的算法的问题。

从一组中查找给出最少浪费的数字

我稍微修改了代码，所以它现在在一定程度上回溯，但输出仍然有缺陷。我已经对此进行了相当多的调试，检查了所有变量值，但似乎无法找出问题。

再次强调，与彻底的解决方案相比，建议会很有帮助。我认为我的代码只有几个问题，但我不知道问题出在哪里。

//来自上一篇文章：

基本上，一个集合被传递给下面的这个方法，并且还传递了一个条形的长度。解决方案应该输出集合中的数字，如果集合中的某些数字是，则该解决方案应该输出最小量的浪费从钢筋长度上去除。因此，条长度为 10，集合包括 6、1、4，因此解为 6 ​​和 4，浪费为 0。我在回溯集合的条件方面遇到了一些麻烦。我还尝试使用浪费“全局”变量来帮助回溯方面，但无济于事。

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

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

package recursivebacktracking;

/**
 *
 * @author User
 */
public class RecBack {

        int WASTAGE = 10;
        int BESTWASTAGE;
        int BARLENGTH = 10;

    public void work()
    {


         int[] nums = {6,1,2,5};
        //Order Numbers
        SetInt ORDERS = new SetInt(nums.length);
        SetInt BESTSET = new SetInt(nums.length);
        SetInt SOLUTION = new SetInt(nums.length);

        //Set Declarration


        for (int item : nums)ORDERS.add(item);
        //Populate Set

        SetInt result = tryCutting(ORDERS, SOLUTION, BARLENGTH, WASTAGE);
        result.printNumbers();


    }
    public SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft, int waste)
      {


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


            int a = possibleOrders.min(); //select next candidate
              System.out.println(a);

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



                if (!possibleOrders.isEmpty()) //solution not complete
                  {
                      System.out.println("this time");
                    tryCutting(possibleOrders, solution, lengthleft, waste);//try recursive call
                    BESTWASTAGE = WASTAGE;
                    if ( BESTWASTAGE <= WASTAGE )//if not successfull
                      {
                        lengthleft += a;
                        solution.remove(a);

                          System.out.println("never happens");
                      }

                  } //solution not complete
              }

          } //for loop

        return solution;

      }




}

Answer 1

您是否考虑过使用位掩码算法而不是使用回溯？我认为这会让你的算法变得更简单。

以下是如何执行此操作的概述：

令 N 为集合中元素的数量。因此，如果集合为 {6,1,2,5}，则 N 将为 4。令 max_waste 为我们可以消除的最大浪费（在您的示例中为 10）。

int best = 0;  // the best result so far

for (int mask = 1; mask <= (1<<N)-1; ++mask) {

    // loop over each bit in the mask to see if it's set and add to the sum
    int sm = 0;
    for (int j = 0; j < N; ++j) {
        if ( ((1<<j)&mask) != 0) {
            // the bit is set, add this amount to the total
            sm += your_set[j];

            // possible optimization: if sm is greater than max waste, then break
            // out of loop since there's no need to continue
        }
    }

    // if sm <= max_waste, then see if this result produces a better one
    // that our current best, and store accordingly
    if (sm <= max_waste) {
        best = max(max_waste - sm);
    }
}

该算法与回溯非常相似，并且具有相似的复杂性，只是不使用递归。

位掩码基本上是二进制表示形式，其中 1 表示我们使用集合中的项目，0 表示我们不使用。由于我们从 1 循环到 (1<，因此我们正在考虑给定项目的所有可能子集。

请注意，随着 N 变大，该算法的运行时间增加得非常快，但当 N <= 20 左右时应该没问题。顺便说一句，同样的限制也适用于回溯。如果您需要更快的性能，则需要考虑另一种技术，例如动态编程。

对于回溯，您只需要跟踪您所在的集合中的哪个元素，然后尝试使用该元素或不使用它。如果使用它，则将其添加到总计中，如果没有，则继续进行下一个递归调用，而不增加总计。然后，您减少总数（如果您增加它），这就是回溯的用武之地。

它与上面的位掩码方法非常相似，我提供了位掩码解决方案来帮助您更好地理解回溯算法的工作原理。

编辑
好吧，我没有意识到你需要使用递归。

提示1
首先，我认为只需使用单个递归函数并将逻辑放入该函数中即可大大简化代码。无需提前构建所有集合然后处理它们（我不完全确定这就是您正在做的事情，但从您的代码来看似乎是这样）。您可以只构建集合，然后跟踪您在集合中的位置。当你完成一组时，看看你的成绩是否更好。

提示2
如果您仍然需要更多提示，请尝试考虑您的回溯函数应该做什么。终止条件是什么？当我们达到终止条件时，我们需要记录什么（例如我们是否得到了新的最佳结果等）？

提示3
剧透警告
下面是一个 C++ 实现，可以为您提供一些想法，因此如果您想自己进行更多操作，请停止阅读此处。

int bestDiff = 999999999;
int N;
vector< int > cur_items;
int cur_tot = 0;
int items[] = {6,1,2,5};
vector< int > best_items;
int max_waste;

void go(int at) {
  if (cur_tot > max_waste)
    // we've exceeded max_waste, so no need to continue
    return;
  if (at == N) {
    // we're at the end of the input, see if we got a better result and
    // if so, record it
    if (max_waste - cur_tot < bestDiff) {
      bestDiff = max_waste - cur_tot;
      best_items = cur_items;
    }
    return;
  }

  // use this item  
  cur_items.push_back(items[at]);
  cur_tot += items[at];
  go(at+1);

  // here's the backtracking part
  cur_tot -= items[at];
  cur_items.pop_back();

  // don't use this item
  go(at+1);
}

int main() {
  // 4 items in the set, so N is 4
  N=4;

  // maximum waste we can eliminiate is 10
  max_waste = 10;

  // call the backtracking algo
  go(0);

  // output the results
  cout<<"bestDiff = "<<bestDiff<<endl;
  cout<<"The items are:"<<endl;
  for (int i = 0; i < best_items.size(); ++i) {
    cout<<best_items[i]<<" ";
  }
  return 0;
}