目錄第二講分治法 2
迴圈賽日程表問題 2
第三講動態規劃 6
矩陣連乘問題 6
最長公共子串行 7
0-1揹包問題 9
最大k乘積問題 11
第四講貪心法 13
揹包問題 13
活動安排問題 14
最優裝載 15
第五講回溯法 18
裝載問題 18
八皇后問題 20
圖的m著色問題 24
第六講分支限界法 27
佈線問題_佇列式 27
0-1揹包問題_佇列式 30
0-1揹包問題_優先佇列式 32
問題描述：設有n=2k個運動員要進行網球迴圈賽。現要設計乙個滿足以下要求的比賽日程表：
（1） 每個選手必須與其他n-1個選手各賽一次；
（2） 每個選手一天只能參賽一次；
（3） 迴圈賽在n-1天內結束。
請按此要求將比賽日程表設計成有n行和n-1列的乙個表。在表中的第i行，第j列處填入第i個選手在第j天所遇到的選手。其中1≤i≤n，1≤j≤n-1。
按分治策略，我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞迴地用這種一分為二的策略對選手進行劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 1 4 3 6 7 8 5
3 4 1 2 7 8 5 6
1 2 3 4 3 2 1 8 5 6 7
1 2 3 4 5 6 7 8 1 4 3 2
1 2 1 4 3 6 5 8 7 2 1 4 3
1 2 3 4 1 2 7 8 5 6 3 2 1 4
2 1 4 3 2 1 8 7 6 5 4 3 2 1
（123）
圖1 2個、4個和8個選手的比賽日程表
圖1所列出的正方形表（3）是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據此，將左上角小塊中的所有數字按其相對位置抄到右下角，又將左下角小塊中的所有數字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在後4天的比賽日程。
依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。
//**如下：
voidmatchtable(inta[n],intk)
]]]}
m*=2;}}
附：p60 2-35
一、問題描述：
設有n個運動員要進行網球迴圈賽。設計乙個滿足以下要求的比賽日程表：
（1）每個選手必須與其他n-1個選手各賽一次；
（2）每個選手一天只能賽一次；
（3）當n是偶數時，迴圈賽進行n-1天。當n是奇數時，迴圈賽進行n天。
二、問題分析和演算法設計：
按分治策略，可以將所有的選手對分為兩組（如果n是偶數，則直接分為n/2每組，如果n是奇數，則取（n+1）/2每組），n個選手的比賽日程表就可以通過為（n/2或（n+1）/2）個選手設計的比賽日程表來決定。遞迴地用這種一分為二的策略對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。
下圖給出的是六個選手的比賽日程表，其中第一列表示1-6個選手，第二列到第六列表示各個選手在第一天到第五天的所遇到的選手。
1 2 3 4 5 6
2 1 5 3 6 4
3 6 1 2 4 5
4 5 6 1 3 2
5 4 2 6 1 3
6 3 4 5 2 1
在這裡演算法設計的難點就是分治後的合併問題。這裡我就結合上面給出的6個選手的示例來進行表述。首先，將6個選手分為對等的兩組，每組3個選手。
然後再遞迴的將3個選手分為對等兩組，每組2個選手。
在2個選手情況下，這兩個選手比賽。可以得到兩個選手的日程安排表是：
1 2
2 1
接下來的任務是合併這兩組2個選手的日程表得到3個選手的日程安排表，這裡我先假設有4個選手參加比賽則：
1 2
2 1
3 4
4 3
接下來的比賽裡，第二天讓1和3比賽，2和4比賽；第三天讓1和4比賽，2和3比賽，即讓前一組的選手，迴圈的和後一組的選手比賽，可得到比賽日程安排表是：
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
這裡要得到的是3個選手的日程安排表，則第4個選手是假想的選手將其用0來表示則得到3個選手的日程安排表：
1 2 3 0
2 1 0 3
3 0 1 2
接下來的任務是合併這兩個3個選手的日程安排表得到6個選手的日程安排表，這裡我們的兩組選手前3天的比賽情況如下：
1 2 3 0
2 1 0 3
3 0 1 2
4 5 6 0
5 4 0 6
6 0 4 5
其中第一天選手3和選手6都沒有對手，讓他們兩個比賽；第二天選手2和選手5沒有對手，讓他們兩個比賽，；第三天選手1和選手4沒有對手，讓他們兩個比賽。這就可以得到合併後6個選手前三天的比賽日程安排表：
1 2 3 4
2 1 5 3
3 6 1 2
4 5 6 1
5 4 2 6
6 3 4 5
將在前三天比過賽的兩組的選手對應的列出來：
1 2 3
4 5 6
在這裡可以看到合併的兩組中3和6，2和5，1和4都已經比過了，這裡就跳過這些選手的比賽，然後兩個組迴圈比賽即：
1 2 3
5 6 4
和 1 2 3
6 4 5
這樣就得到了6個選手的比賽完整的日程安排表：
1 2 3 4 5 6
2 1 5 3 6 4
3 6 1 2 4 5
4 5 6 1 3 2
5 4 2 6 1 3
6 3 4 5 2 1
三、證明演算法的正確性：
（1）在n=2時，就這兩個選手比賽，比賽只進行一天，這也是演算法的初始情況，演算法成立。
貪心演算法經典例題
所謂貪心演算法指的是為了解決在不回溯的前提之下，找出整體最優或者接近最優解的這樣一種型別的問題而設計出來的演算法。貪心演算法的基本思想是找出整體當中每個小的區域性的最優解，並且將所有的這些區域性最優解合起來形成整體上的乙個最優解。因此能夠使用貪心演算法的問題必須滿足下面的兩個性質 1.整體的最優解可...
經典濾波演算法及C語言程式
經典的濾波演算法 a 方法 根據經驗判斷，確定兩次取樣允許的最大偏差值 設為a 每次檢測到新值時判斷 如果本次值與上次值之差 a,則本次值有效 如果本次值與上次值之差 a,則本次值無效,放棄本次值,用上次值代替本次值 b 優點 能有效克服因偶然因素引起的脈衝干擾 c 缺點 無法抑制那種週期性的干擾 ...
經典pso粒子群優化演算法程式
clear all清除所有變數 clc清屏 format long將資料顯示為長整形科學計數 給定初始條條件 n 40初始化群體個數 d 10初始化群體維數 t 100初始化群體最迭代次數 c11 2學習因子1 c21 2學習因子2 c12 1.5 c22 1.5 w 1.2慣性權重 eps 10 ...