递归回溯问题

Question

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

Finding the numbers from a set which give the minimum amount of waste

伊夫修正代码略，所以现在回溯到一定程度，然而，输出仍存在缺陷。我调试了这大幅检查所有的变量值，似乎无法找出问题。

再次建议，而不是一个彻底的解决方案将有很大的帮助。我认为我的代码只有几个问题，但我无法解决问题。

从以前的帖子//：

基本上是一组被传递到低于该方法和条的长度也被所述的溶液通过应输出从所述一组这给的最小量的数字。如果集合中的某些数字从长度上移除，则浪费。因此，条的长度为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)-1，我们正在考虑给定项目的所有可能的子集。

请注意，此算法的运行时间随着N变大而增加得非常快，但在N大约为20时应该没问题。顺便说一句，跟踪跟踪也适用同样的限制。如果你需要更快的性能，你需要考虑另一种技术，如动态编程。

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

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

编辑 好的，我没有意识到你被要求使用递归。

提示1 首先，我认为只需使用一个递归函数并将逻辑放在该函数中就可以大大简化代码。没有必要提前构建所有集合，然后处理它们（我不完全确定那是你在做什么，但它似乎来自你的代码）。你可以建立这些集合，然后跟踪你在集合中的位置。当你到达集合的末尾时，看看你的结果是否更好。

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

Hint3 尾翼警报 下面是一个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; 
}