集和的演算法

『壹』 近似演算法的子集和問題的近似演算法

問題描述：設子集和問題的一個實例為〈S,t〉。其中，S={x1，x2，…，xn}是一個正整數的集合，t是一個正整數。子集和問題判定是否存在S的一個子集S1，使得∑x = t。(x屬於S1)
1 子集和問題的指數時間演算法
int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1；i<=n；i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
刪去L[i]中超過t的元素；
}
return max(L[n])；
}
演算法以集合S={x1，x2，…，xn}和目標值t作為輸入。演算法中用到將2個有序表L1和L2合並成為一個新的有序表的演算法mergeLists(L1,L2)。
2 子集和問題的完全多項式時間近似格式
基於演算法exactSubsetSum，通過對表L[i]作適當的修整建立一個子集和問題的完全多項式時間近似格式。
在對表L[i]進行修整時，用到一個修整參數δ，0<δ<1。用參數δ修整一個表L是指從L中刪去盡可能多的元素，使得每一個從L中刪去的元素y，都有一個修整後的表L1中的元素z滿足(1-δ)y≤z≤y。可以將z看作是被刪去元素y在修整後的新表L1中的代表。
舉例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，則用δ對L進行修整後得到L1=〈10，12，15，20，23，29〉。其中被刪去的數11由10來代表，21和22由20來代表，24由23來代表。
對有序表L修整演算法
List trim(L,δ)
{ int m=|L|；
L1=〈L[1]〉；
int last=L[1]；
for (int i=2；i<=m；i++) {
if (last<(1-δ)*L[i]) {
將L[i]加入表L1的尾部；
last=L[i]；
}
return L1；
}
子集和問題近似格式
int approxSubsetSum(S,t,ε)
{ n=|S|；
L[0]=〈0〉；
for (int i=1；i<=n；i++) {
L[i]=Merge-Lists(L[i-1],
L[i-1]+S[i])；
L[i]=Trim(L[i],ε/n)；
刪去L[i]中超過t的元素；
}
return max(L[n])；
}

『貳』 並集和交集的公式是什麼

交集？並集？

你還記得高中數學的第一課嗎？講的是集合，具體定義去網路，裡面有兩個運演算法則：交集和並集。也許你當時覺得很容易，那麼今天還是回頭想想它在講什麼。

一、兩個集合

一切運算都是兩個相對的集合間的關系法則，既然是高中數學，那麼就略談一下教育，其實很多人會說「你考好了說明學好了」，然而我想說的是考試和教學是兩個集合。

我們看看中國過去的八股文，包括今天的高考，受到那麼多詬病，但是為什麼還是繼續這么做？因為相關部門不知道，無作為？我覺得要是從另外一個角度看，考試作為一種人才選拔的工具，那選拔什麼樣的人呢？是見多識廣、才華橫溢的人；還是那些面對一個目標，能持之以恆地找方法達成，坐得住、能下功夫的人呢？

不好意思，答案很可能是後者。

現在很多創業公司都有這樣的體會。招人的時候，他們往往不是傾向於招那些有經驗的人，而傾向學習能力好、溝通能力強、對自己要求嚴、有自我驅動能力的人。因為創業公司本來做的就是全新的事情，經驗這個東西是有益還是有害，說不清楚。但是面對任何新的情況，都能找到方法、訴諸行動、不丟目標的人，才是創業公司需要的。前一陣還有一位創業公司的創始人跟我說，他發現優秀的大學生，比行業里的老鳥好用。

這種優秀的人，不管面對什麼樣的題目，哪怕是八股文，也一樣可以坐得住、下苦功，最後考出好成績。這樣的人走入仕途，面對自己不熟悉的任務，也一樣會表現優秀。事實上，明清兩代那麼多能人都是靠八股文選拔出來的，比如我們熟悉的王陽明和曾國藩。

再回頭來說我們的高考。

這幾年，高考的發展趨勢和八股文正好相反的，這也是很多人呼籲和推動的結果。各地高考越來越強調地方特色，越來越多地考核學生的所謂「綜合素質」。這種發展方向看似正確，但是也有值得反思的地方。

首先，中國是一個大國，各地情況差異巨大，社會階層也差異巨大。只有堅持全國的統一性，才能確保人才通過高考在全國范圍內的流動和交流，維持整個國家的內在聯系和國家認同。不誇張地說，如果高考的全國統一性消失了，中國各個地方的內在聯系會被嚴重削弱。

我們不能把高考僅僅看作是教育的一個環節，高考是國家治理中的關鍵，事關國家的完整統一和治理水平。

其次，雖然不必恢復到八股文那樣死板的形式，但高考仍然要盡量維持簡單、明晰的考試內容和形式。一言以蔽之，永遠要確保，學生只靠幾本教科書、只比拼硬功夫、笨功夫就能取得好成績。

和科舉一樣，高考不是教育工具，高考是人才選擇的工具。它把各個社會階層里奮發向上，能坐得住、下苦功夫的人挑選出來，保持這個社會的活力和公平。這才是高考在當前中國社會的真實作用。

然而，所謂教育則是一種能力的培養，一種思維模式的鍛煉，比如我們講集合，你不光會做題還要會應用，比如將學習數學思維和考試分開來，當然它們之間有交集，就是你既能坐下來刷題總結，又能進行發散和轉化，你要既能學好集合又能考好集合這就是交集，而你只是明白自己要好好學習並且考試優異這就是並集。其實大多數人在看問題的時候喜歡用並集，這樣比較省事，也符合原始的認知方式，然而今天這種方式與時代有所不匹配啦，這種人就是那些現在邊緣只求安全感，卻不願多向集合內多走一步深入了解的人。我們在許多問題上可以有所區分，比如人工智慧就是未來一切的引導？關系問題一定是其中一個人有問題或者兩個人有問題？

二、人工智慧就是人類的全部模擬？

這個的答案明顯是否定的，人工智慧是完全通過演算法運行的，這些演算法都來自於各個學科的模型計算，你去翻翻書，所以學科都有一個所謂的理想假設，這個假設通俗的講就是，如果世界只有XX學科來指導運行的話。所以人工智慧可以模擬任意學科，但是這是不同的集合，交集並不能完全模擬，對於這個問題，很多人認為只要融合了那麼交集自然呈現啊，其實不然。舉個例子，一些有經驗的心理咨詢師在處理感情糾葛問題時，會說他面對的是三個人，夫妻雙方和他們的關系，而關系就是交集的結果，所以關系問題不一定是個人或者兩個人的問題導致，也有可能是他們的交集，也就是產生的關系導致。再者人工智慧更偏向科學，而科學思維和技術僅僅是社會中的小部分，還有大部分的人性，也就是社會科學，例如人工智慧的圍棋站，輸的那一局就是輸在人性上，所以任何復雜問題回答時，可以考慮下是否存在兩個及以上集合，因為可能存在第三者。（上述問題因本文需求，不多做拓展）這樣一個是非問題只有兩個答案，卻可能有三層認知。

三、認知三級跳

最近中子星的新聞應該都看過了，那麼問個看問題，宇宙是有限的還是無限的？如果回答宇宙是有限大的，那說明這個人具備了一定的科學素養。如果他回答宇宙是無限大的，那就有兩種可能。一種可能是這個人對現代科學一無所知；另一種可能，卻是他對天體物理學的最新進展非常了解。

第一層，無限大，從小就知道宇宙浩瀚無邊，沒有天邊，所以無限大。

第二層，有限大，知道宇宙大爆炸，就知道宇宙是個正在被吹大得氣球，不管怎麼變大，氣球總還是有邊界的，於是有限大。

第三層，無限大，根據2013最新發現，宇宙質能比例系數為1±0.004，以及宇宙背景輻射的數據，證明在歐幾里得空間內，宇宙是一個平面，無限延伸。

那麼又會出現一個特別有意思的情況，二八理論，如果去統計下會發現中間層的人會有80%，所以當你和很多別人的觀點一樣的時候就要警惕啦，你是不是中間層？你也許離出現集合只有一步，而你卻沾沾自喜。

同樣的事情我們看看對朋友圈的認識，最早用的時候，很多人不習慣的，認為不好所以希望不要有。當發現裡面信息多樣化，被設計吸引後，幾乎大多數人都愛它。而像我自從寫出那篇朋友圈是黑暗森林後，至今朋友圈沒看過，而我並沒有過不下去，或者對我的生活學習工作沒有太大影響，那我還去看了幹嘛，花去巨大的時間成本，卻基本沒有收益啊。

『叄』 演算法的子集和數問題

回溯演算法設計2008-05-29 10:15 P.M.[實驗目的]

1. 掌握回溯法解題的基本思想；

2. 掌握回溯演算法的設計方法；

3. 針對子集和數問題，熟練掌握回溯遞歸演算法、迭代演算法的設計與實現。

[預習要求]

1. 認真閱讀教材或參考書, 掌握回溯法解題的基本思想, 演算法的抽象控制策略；

2. 了解子集和數問題及解向量的定長和變長狀態空間表示；

3. 針對解向量的定長表示, 設計狀態空間樹節點擴展的規范(限界)函數及實現方法；

4. 分析深度優先擴展狀態空間樹節點或回溯的條件；

5. 分析和設計生成解向量各分量可選值的實現方法；

6. 設計和編制回溯演算法的遞歸和迭代程序。

[參考數據類型或變數]

float s; // 表示有可能抵達答案節點的子路徑上的元素之和；

float r; // 尚未測試的剩餘集合元素之和；

float w[n]; // 存儲原始集合的n個元素, 根據問題實例初始化；

int x[n]; // 定長表示的解向量, 各元素初始值為0；

[參考子程序介面與功能描述]

void RecursiveSubset(float s, float r, int k)

功能: 針對問題實例的遞歸回溯演算法。

void IterativeSubset(int m)

功能: 針對問題實例的迭代回溯演算法。

void InitializeInstanse(void)

功能: 問題實例的初始化函數, 初始化子集和數M , w, x向量, s, r。

[實驗步驟]

1. 錄入、修改並測試你的程序，直至正確為止；

2. 針對問題實例，實錄運行時的輸入、輸出界面；

3. 將你的程序和實錄的界面存檔備用。

[實驗報告要求]

1. 闡述實驗目的和實驗內容；

2. 提交模塊化的實驗程序源代碼；

3. 簡述程序的測試過程，提交實錄的輸入、輸出界面；

4. 鼓勵對實驗內容展開討論，鼓勵提交思考與練習題的代碼和測試結果。

[思考與練習]

1. 試針對解向量的變長表示設計回溯演算法，上機測試正確性。

2. 試針對0/1背包問題設計回溯演算法，比較與子集和數問題的演算法差異。

#include<stdio.h>
#define n 3
float s; /*表示有可能抵達答案節點的子路徑上的元素之和；*/
float r; /*尚未測試的剩餘集合元素之和；*/
float w[n]={2,3,4}; /*存儲原始集合的n個元素, 根據問題實例初始化；*/
int x[n]; /*定長表示的解向量, 各元素初始值為0；*/
int M;
int k;

void RecursiveSubset(float s, float r, int k)/*針對問題實例的遞歸回溯演算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}

else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*針對問題實例的迭代回溯演算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*問題實例的初始化函數, 初始化子集和數M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");