題目：20個桶，每個桶中有10條魚，用網從每個桶中抓魚，每次可以抓住的條數隨機，每個桶只能抓一次，問一共抓到180條的排列有多少種 （也可求概率）。 分析一下 這道題其實可以這樣理解，假設我已經抓到了180條魚，而這180條魚來自20個桶中，反過來就是我們將這180條魚放到20個桶中且要保證每個桶的魚在（0-10）之間，有多少種方法。假設我們在前i個桶中抓取了k（0<=k<=10*i）條魚，那麼抓取180條魚的排列種數就等於在剩下的（20-i）個桶中抓取（180-k）條魚的方法加上前i個桶中抓取k條魚的方法。 再想一下 由於總共有200條魚，我們抓走了180條魚，那麼還剩下多少條呢？顯然是20條。再用上面的思維，我們就可以這樣想，將20條魚放回這20個桶中滿足每個桶中的魚（0-10），有多少種放法。這裡當然是因此了一個排列問題而不是組合問題，因為我第一個桶放1條魚、第2個桶不放與第一個桶不放、第二個桶放1條魚，是兩種的不同的放法。 這樣分析下來，感覺就是一個跳台階問題：一個梯子有20步，每次可以跳0-10步，20步跳完多少中跳法（可選擇不跳）。 編程思想 思想其實跟完全背包問題類似，我們首先考慮第20個桶放多少魚，那麼我們就可以減去最後一個桶放的魚數，再去考慮前面19個桶怎麼放剩下的魚。這樣形成了一個遞歸，我們就可以很快寫出如下代碼。 [cpp] //bucket，表示當前考慮到第幾個桶，當然首先考慮第20個桶 //fishN，表示當前有多少魚 //返回值表示有多少中方法 int Func(int bucketN,int fishN) { if(bucketN<0 || fishN<0)return 0;//錯誤處理 if(bucketN == 1){ if(fishN>=0 && fishN<=10)//第1個桶裡面放0-10的魚，方法只有一種 return 1; else{ return 0; //其他用0種方法 } } int sum = 0; for(int i=0; i<=10; ++i){ sum += Func(bucketN-1,fishN-i);//考慮前面bucket-1的組合，同時減掉當前放的魚 } return sum; } 遞歸優化 上面的代碼，其實有很多重復計算。下面我們簡單的分析一下： F(20，20) = F(19，19)+ F(19，18).......; //考慮第20個桶放一條魚和兩條魚的情況 F(19，19) = F(18，17)+.....;//第19個桶放2條魚 ① F(19，18) = F(18，17)+.....;//第19個桶放1條魚 ② 我們發現①和②都調用了F(18，17)，但是它們確實各算各的，這樣就存在著很多類似的重復計算。該遞歸樹，基本全是重復的點，這樣時間復雜度被拖得很高。那麼，我們只要設計一個數組來把計算好的值保存下來，這樣避免了很多重復的計算。代碼如下： [cpp] //bucket，表示當前考慮到第幾個桶，當然首先考慮第20個桶 //fishN，表示當前有多少魚 //返回值表示有多少中方法 int dp[21][200] = {0}; int FuncOptimize(int bucketN,int fishN) { if(bucketN<0 || fishN<0)return 0; if(bucketN == 1){ if(fishN>=0 && fishN<=10) return 1; else{ return 0; } } if(dp[bucketN][fishN] == 0){ //這個子過程沒有被計算我們采取調用遞歸計算 for(int i=0; i<=10; ++i){ dp[bucketN][fishN] += FuncOptimize(bucketN-1,fishN-i); } } return dp[bucketN][fishN]; } 下面我們用我們熟悉的斐波拉契序列做一個實驗，我們同樣的優化方式來做，看下程序跑得快了多少? [cpp] #include<iostream> #include <windows.h> using namespace std; long long fibonacci[100]; long long Fibonacci(int n) { if(n == 0)return 1; if(n == 1)return 1; return Fibonacci(n-1) + Fibonacci(n-2); } long long FibonacciOptimize(int n) { if(n == 0)return 1; if(n == 1)return 1; if(fibonacci[n] == 0){ fibonacci[n] = FibonacciOptimize(n-1) + FibonacciOptimize(n-2); } return fibonacci[n]; } int main() { DWORD seconds = GetTickCount(); cout<<Fibonacci(40)<<endl; cout<<"優化之前："<<(GetTickCount() - seconds)<<"ms"<<endl; seconds = GetTickCount(); cout<<FibonacciOptimize(40)<<endl; cout<<"優化之後："<<(GetTickCount() - seconds)<<"ms"<<endl; system("pause"); return 0; } 這個結果很是滿意啊。 動態規劃實現 我們知道這種自頂向下的遞歸，都可以轉換為動態規劃自底向上的思想。就是我們遞歸的值是有下面的值一步步壘起來的，那麼我只需要一開始就把下面的值算好，保持在那裡，然後再算上面的時候，直接拿過來用，這就很快了。據我了解，背包問題的編程思路跟這道題是一摸一樣，只不過背包走到第i種物品的時候，第i種物品的重量已經固定，而我們這道題是第i個桶取值是一個范圍，那我們只要把這裡范圍都掃一遍就好了。 [cpp] #include<iostream> #include <windows.h> using namespace std; int dp[21][200] = {0}; int FuncDp(int bucketN,int fishN) { int i,j,k; for(i=0; i<=10; ++i) dp[1][i] = 1; for(i=2; i<=bucketN; ++i){ for(j=0; j<=fishN; ++j){ for(k=0; k<=10&&j-k>=0; ++k){//可以取0-10 dp[i][j] += dp[i-1][j-k]; } } } return dp[bucketN][fishN]; } int main() { cout<<FuncDp(20,180)<<endl; memset(dp,0,sizeof(dp)); cout<<FuncDp(20,20)<<endl; system("pause"); return 0; } 其實，代碼還可以更簡練，仔細想想，就是初始化狀態的方法；其實初始化合法狀態完全可以這樣想，問題始終都是分解成子問題的，根據遞歸的實現方法，只有分解到0個桶裝0條魚才是合法的，那麼我們就初始化這一個狀態為合法即可，然後從第一個桶開始向上計算，代碼如下： [cpp] #include <iostream> using namespace std; int dp[21][200]; int i, j, k; void main() { int bucketN, fishN; scanf("%d %d", &bucketN, &fishN); dp[0][0] = 1; /* 初始化合法狀態 */ for(int i = 1; i <= bucketN; ++i) /* 從第一個桶開始 */ { for(int j = 0; j <= fishN; ++j) { for(int k = 0; k <= 10 && j-k >= 0; ++k) { dp[i][j] += dp[i-1][j-k]; } } } printf("%d\n",dp[bucketN][fishN]); } 想不通我的空間優化怎麼不成功，類似背包問題的優化，555555555555555555。有大神可以幫忙解釋一下啊？ [cpp] #include<iostream> #include <windows.h> using namespace std; int dp[200] = {0}; int FuncDp(int bucketN,int fishN) { int i,j,k; for(i=0; i<=10; ++i) dp[i] = 1; for(i=2; i<=bucketN; ++i){ for(j=fishN; j>=0; --j){//反著遍歷，防止覆蓋 for(k=0; k<=10&&j-k>=0; ++k){//可以取0-10 dp[j] += dp[j-k]; } } } return dp[fishN]; } int main() { cout<<FuncDp(20,180)<<endl; memset(dp,0,sizeof(dp)); cout<<FuncDp(20,20)<<endl; system("pause"); return 0; }
