递归回溯的问题

嘿伙计们，最近发布了我的算法问题。

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

我略微修改了代码，所以它现在回溯到一定程度，但输出仍然存在缺陷。 我已经调试了这个大大调查所有变量值，似乎无法找出问题。

与直接解决方案相反的建议再次提供了很大的帮助。 我认为我的代码只有几个问题，但我无法解决问题。

//来自上一篇文章：

基本上，一个集合被传递给下面的这个方法，并且还传入一个条形的长度。解决方案应该输出集合中的数字，如果从条形长度中移除了集合中的某些数字，则给出最小量的浪费。 因此，条形长度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< 

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

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

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

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

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

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

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

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

Hint3 Spoiler Alert下面是一个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 = "<