Re: [問題] 分割數問題 (n相同物放入m相同箱, 可空)

看板C_and_CPP (C/C++)作者ppc (Stand by me)時間14年前 (2012/01/24 04:04)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《redsmallbo (紅色小波)》之銘言： : 問題(Question)： : 這是"培養與鍛鍊程式設計的邏輯腦"(一本書)中第71頁的題目: : 請求出將n個無法互相區別的物品分割成m個以下的方法之總數， : 以及除以M之後的餘數。 : 原題目的文字敘述不是很好懂， : 可以將題目理解為: : 將n個相同物放入m個相同箱，允許有空箱的方法數s， : s除以M的餘數即為答案。 : 餵入的資料(Input)： : n = 4 : m = 3 : M = 10000 : 預期的正確結果(Expected Output)： : 4 : 錯誤結果(Wrong Output)： : 9 : 程式碼(Code)：(請善用置底文網頁, 記得排版) : 好讀版: http://codepad.org/52BGIUYa : #include <iostream> : #include <fstream> : using namespace std; : // file : fstream fin("sample.in"); : // constant : const static int MAX_N = 1000; : const static int MAX_M = 1000; : // input : int n, m, k; : // output : int dp[MAX_M + 1][MAX_N + 1]; : int main() : { : // input : fin >> n >> m >> k; : // solve : dp[0][0] = 1; : for (int i = 1; i <= m; ++i) : for (int j = 0; j <= n; ++j) : dp[i][j] = (j >= i) ? (dp[i - 1][j] + dp[i][j - 1]) % k : dp[i - 1][j]; j < i => 球的數目(j)小於箱子數目(i) 所以一定有i-j個箱子一定沒有球 => 所以問題等於 j個球放入 j個箱子 => dp[i][j]=dp[j][j] j >=i => 球的數目(j)多於箱子數目(i) 問題可拆解如下 => A: 每個箱子都放入一個球問題變成 j-i個球放入i個箱子 dp[i][j-i] (每個箱子一定都有球) B: 其中一個箱子一定不放球問題變成 j個球放入i-1個箱子 dp[i-1][j] (至少一個箱子沒有球) 而 A∩B=ψ A∪B=j個球放入i個箱子 => dp[i][j]=(dp[i - 1][j] + dp[i][j - i])%k Hence, dp[i][j] = (j >= i) ? (dp[i - 1][j] + dp[i][j - i]) % k : dp[j][j]; : // output : cout << dp[m][n] << endl; : return 0; : } : 補充說明(Supplement)： : 這章是在交 dp 解， : code 是參考書本上的 code，稍微修改， : 但演算法內容不變。 -- 大家都討厭妓者卻有時候完全相信妓者的寫的報導其實就只是說明大家都挑自己想相信的去相信而已 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.241.92.249 ※ 編輯: ppc 來自: 210.241.92.249 (01/24 04:06)