199管綜——分組分配問題

長春學子 · 發表于 2020-6-22 17:41

例．將3封信投入4個不同的信箱,則不同的投信方法種數是多少？
這是一個典型的分房問題，3個人4間房，每個人都有4種選擇，所以結果就是3個4相乘，是4^3，也就是“房”的“人”次方。非常簡單的一類問題，但是其中卻隱藏著很多的條件，主要是以下6個：
1.房是不同的(組別或編號)
2.人是不同的(元素是否相同)
3.房子的容量是無限的（1對多）
4.一個人只能住到一個房子里（1對1）
5.房子可以空(組內元素數是否可以為0)
6.人必須都住到房子里（是否分盡）
下面分別給大家介紹一下每個條件的運用：
1. 房是不同的，這個限定條件在分組問題上體現為是否有組別或者編號，如果房間是相同的沒有區別，那么就會比房間不同的情況分類要少，因為會出現重復的情況。
2. 人是不同的，這說明分配的元素是不相同的，如若元素相同，那么每個組的區別可能就體現在元素的數量上了。
3. 房子的容量是無限的，這是分組問題一個很重要的條件，就是每個組的人數沒有限制，所有人都可以在一個組，而這個組的元素數量沒有上限。
4. 一個人只能住到一個房子里，這個同樣也是一個很重要的條件，結合上面的條件（3），如果一間房只能容納一個人，而一個人只能住到一個房子里，那么這個問題轉化成了排列組合的問題，“一對一”是排列組合問題的基本要求。
5. 房子可以空，也就是組內元素數是否可以為0 的情況，這個在實際中會有這樣的問題，如果把10個元素分成三組，三組元素數如果是5，5，0的情況，那么我們們會理解成分成了兩組，如果認為有一組是0的話，那么也可以理解成分為4組或更多組，其他組的元素數為0，這個就會有些沖突。
6. 人必須都住到房子里，這個條件所分元素是否分盡，沒有分盡的話，我們要討論分了多少，也即是分盡了多少，還是轉移到分盡的情況之下。
上面6條就是根據分房問題的隱含條件進行了分析，也是構成分組問題的基礎，根據更
改不同的條件把分組問題分成不同的類型，一般條件（3）和（4）是不變的，因為是構成分組問題的基礎，如果改變那么很有可能就不是分組問題而是排列組合問題或者其他問題了，下面我們改變一些條件，討論下常見的兩種分組類型：
1.保留條件（2），這個時候問題變成了不同元素的分組問題，根據是否改變條件（1），又分成是否有編號的兩類不同元素分組，不同元素分組問題一般會確定每組人數，也就是條件（5）組內元素數是固定的，這個時候又根據任意每兩組人數是否相同分為均勻分組和不均勻分組，至于條件（6）是否分盡，對于不同元素分組問題是沒有影響的。
2.保留條件（1），改變條件（2），這個時候變成了相同元素分組的問題，這種問題一般選用隔板法去做，比起不同元素的分組問題，相同元素的分組問題有著更嚴格的要求，比如條件（5）要求每組至少有一個人，而條件（6）要求必須分盡。

阿萊moon · 發表于 2020-6-29 09:14

太有幫助了

考霸霸霸霸霸霸 · 發表于 2020-9-14 13:24

太有幫助了

		自動登錄	找回密碼
密碼			注冊

199管綜——分組分配問題

NEW最新資料推薦