遞歸回溯問題

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; 
}