解法框架

【README】回溯算法基本框架

幸運的袋子(點擊跳轉)

這道題基本也是回溯，題解中有一部分提到了dfs，其實dfs本質也是回溯算法。這道題有點特別，除了考察算法外，還輕微涉及一點數學知識，其實也可以說是規律吧。此題本質就是在集合中找到符合條件的子集，這條件就是子集中所有數字的和大于所有數字的積

規律如下

數論中：對于兩個任意的正整數a和b，如果要滿足a+b<ab，則必須要有一個數為1

我們將所有的球排好序后，假設a1，a2，a3不滿足條件，那么也就是sum<=multi，如果要選擇一個數b使得sum+b>multi*b，那么b一定為1。但是如果選擇的b>1，那么一定不滿足條件，同時排在b后面的數組更不可能滿足條件

如果有連續的1存在，且當前位置不滿足條件，但是該位置的數字為1，那么應該繼續向后找尋，因為只要是1就能增大sum，而不會使multi變大

對于重復的數字只算一次，也就是咋們在回溯算法中說到過的在選擇列表中選擇正確的選項

首先，這道題要完全自己輸入和輸出，先打起框架。咋們的選擇列表，也就是所有球的編號，依次存放在一個vector中，接著將球按照編號從小到大的排序

#include <iostream> #include <vector> #include <algorithm> using namespace std;int main() {int n;//接受幾個球cin>>n;vector<int> ball;for(int i=0;i<n;i++){int temp;cin>>temp;ball.push_back((temp));}sort(ball.begin(),ball.end());//排序}

選擇列表有了，下一個就是路徑，這個路徑非常簡單，只需要一個整型ret即可，因為當sum>multi的時候，這表明現在就已經可以作為一個幸運的袋子了，所以ret增加。 所以將ret設置為全局變量。

對于遞歸函數，第一個參數一定是選擇列表，第二個參數是球的個數，第三個參數要設置為一個pos，因為遞歸函數進行for循環時一定要一個正確的起始位置，for循環每次就從i=pos的位置，遞歸時這個球加入了，我們就pos=i+1，表明選擇下一個球。剩下兩個參數分別為sum和multi用于計算判斷

int ret=0;//幸運的袋子個數 void back(vector<int>& ball,int n,int pos,int sum,int multi) {for(int i=pos;i<n;i++){sum+=ball[i];//和multi*=ball[i];//乘積if(sum>multi)//ball[i]這個球加入后符合幸運袋子{ret+=1;back(ball,n,i+1,sum,multi);//繼續回溯，下一個位置}else if(ball[i]==1)//如果不滿足條件，但是這一位是1，是還有機會的，所以遞歸就可以了{back(ball,n,i+1,sum,multi);}else{break;//不滿足直接退出}sum-=ball[i];//撤銷選擇multi/=ball[i];//撤銷選擇while(i<n-1 && ball[i]==ball[i+1])//連續的只選擇1次{++i;}}}

需要注意的是去重要寫在后面，不要一上來就去重

最后完善即可，注意multi在傳入時要傳入1，不要傳入0

#include <iostream> #include <vector> #include <algorithm> using namespace std;int ret=0;//幸運的袋子個數 void back(vector<int>& ball,int n,int pos,int sum,int multi) {for(int i=pos;i<n;i++){sum+=ball[i];//和multi*=ball[i];//乘積if(sum>multi)//ball[i]這個球加入后符合幸運袋子{ret+=1;back(ball,n,i+1,sum,multi);//繼續回溯，下一個位置}else if(ball[i]==1)//如果不滿足條件，但是這一位是1，是還有機會的，所以遞歸就可以了{back(ball,n,i+1,sum,multi);}else{break;//不滿足直接退出}sum-=ball[i];//撤銷選擇multi/=ball[i];//撤銷選擇while(i<n-1 && ball[i]==ball[i+1])//連續的只選擇1次{++i;}} }int main() {int n;//接受幾個球cin>>n;vector<int> ball;for(int i=0;i<n;i++){int temp;cin>>temp;ball.push_back((temp));}sort(ball.begin(),ball.end());//排序back(ball,n,0,0,1);cout<<ret<<endl;return 0;}

總結

以上是生活随笔為你收集整理的回溯算法之幸运的袋子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。