謹(jǐn)以此文，感謝我在這個(gè)學(xué)校最喜歡的兩個(gè)老師之一——肖my老師步责。本文基本為老師上課說講授內(nèi)容加上一部分自己的感悟拼湊而來返顺，寫作文本的目的是為自己的算法課程留下一點(diǎn)點(diǎn)東西禀苦，站在老師肩膀上形成粗糙的框架，方便以后的復(fù)習(xí)以及深入遂鹊。文筆有限振乏，其中包含的錯(cuò)誤還請多多包容，不吝賜教秉扑。

to do list：

時(shí)間復(fù)雜度中遞歸樹法慧邮；動(dòng)規(guī)，分治新的感悟舟陆；

一：基礎(chǔ)

部分算法误澳、概念的前置知識

點(diǎn)覆蓋：一組點(diǎn)的集合，使得圖中所有邊都至少與該集合中一個(gè)點(diǎn)相連吨娜。

支配集：一組點(diǎn)的集合脓匿，使得圖中所有的點(diǎn)要么屬于該集合，要么與該集合相連宦赠。

最大團(tuán)：在一個(gè)無向圖中找出點(diǎn)數(shù)最多的完全圖。

獨(dú)立集：一組點(diǎn)的集合米母，集合中的頂點(diǎn)兩兩不相鄰勾扭。（團(tuán)轉(zhuǎn)過來）

SAT問題：也稱布爾可滿足性問題。給一組變

其中Ci被稱為句子身辨。

點(diǎn)覆蓋<->獨(dú)立集<->最大團(tuán)

最小割：割是一組邊集。如s-t割就是如果去掉這些邊芍碧，將把原圖劃分為兩個(gè)點(diǎn)集煌珊，其中一個(gè)點(diǎn)集包含s，一個(gè)點(diǎn)集包含t泌豆。（兩個(gè)是指不相連定庵，而不是代表不存在邊相連，如反向邊）

decision problem: 是否存在踪危。

search problem:找到一個(gè)解蔬浙。

（這個(gè)還能擴(kuò)展，比如decision problem在多項(xiàng)式時(shí)間內(nèi)解決贞远，所以他是P問題嗎）

漸進(jìn)符號：

注意以上三種都是緊的畴博，對應(yīng)的兩個(gè)小寫的符號是不緊的，即如下圖所示：

時(shí)間復(fù)雜度

概念：算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)蓝仲，用于定性描述算法的運(yùn)行時(shí)間俱病。注意蜜唾，這個(gè)一個(gè)代表算法輸入字符串長度的函數(shù)。

[注]輸入字符串長度是一個(gè)比較關(guān)鍵的理解庶艾，比如在背包問題中袁余，其時(shí)間復(fù)雜度為O(nW)，因?yàn)閃不定咱揍，所以只能是一個(gè)偽多項(xiàng)式時(shí)間颖榜。

比較：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n

大致：常數(shù)<對數(shù)<冪函數(shù)<指數(shù)函數(shù)<階乘

對于指數(shù)是n相關(guān)的進(jìn)行比較，優(yōu)先比較指數(shù)煤裙，再比較底數(shù)掩完。

記住一個(gè)特例：n^(logn)<n!<nn

計(jì)算：

一般來說，計(jì)算采用主方法和遞歸樹法硼砰，其中遞歸樹技巧性比較強(qiáng)且蓬，主方法其實(shí)也是遞歸樹推導(dǎo)歸納而來，且主方法能得到一個(gè)比較緊的結(jié)果题翰。

主方法：

f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )

P恶阴，NP，NP-Complete和NP-Hard

P：decision problems有一個(gè)多項(xiàng)式算法豹障。

NP（nondeterministic polynomial-time）：decision problems能夠在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證冯事。

NPC：NP完全問題，首先這個(gè)問題是NP的血公，其次昵仅，其他所有問題都可以多項(xiàng)式時(shí)間內(nèi)歸約到它。

NPH：如果所有NP問題都可以多項(xiàng)式時(shí)間歸約到某個(gè)問題累魔，則稱該問題為NP困難摔笤。

因?yàn)镹P困難問題未必可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解的正確性（即不一定是NP問題），因此即使NP完全問題有多項(xiàng)式時(shí)間的解（P=NP）垦写，NP困難問題依然可能沒有多項(xiàng)式時(shí)間的解吕世。因此NP困難問題“至少與NP完全問題一樣難”。

一些NP問題能在多項(xiàng)式時(shí)間內(nèi)解決梯澜，因?yàn)?P∈NP

NP難類型問題的證明：

先選好一個(gè)已知NP難的問題寞冯，然后將已知NP難問題多項(xiàng)式歸約到要證明的問題上。先給出這個(gè)歸約晚伙，然后再證明這個(gè)歸約的正確性吮龄。

NPC類型問題的證明：

證明一個(gè)問題Y是NPC問題，先說明Y是NP的咆疗，然后找到一個(gè)NPC問題X漓帚，將這個(gè)問題X歸約到問題Y上，即證明完成午磁。

常見的NPC問題（重要尝抖，規(guī)約的時(shí)候有用Ｕ泵恰）：

packing problems: set-packing，獨(dú)立集

覆蓋問題：集合覆蓋問題昧辽，頂點(diǎn)覆蓋問題

嚴(yán)格滿足問題(constraint satisfaction problems)：SAT衙熔，3SAT

序列問題：哈密爾頓回路，旅行商問題

劃分問題：3D-matching, 3著色問題

數(shù)字問題：子集合問題（子集元素之和為t）搅荞，背包問題

其他：分團(tuán)問題（是否存在一個(gè)規(guī)模為k的團(tuán)）

規(guī)約的概念與理解

規(guī)約：意味著對問題進(jìn)行轉(zhuǎn)換红氯，例如將一個(gè)未知的問題轉(zhuǎn)換成我們能夠解決的問題，轉(zhuǎn)換的過程可能涉及到對問題的輸入輸出的轉(zhuǎn)換咕痛。

自歸約：search problem <=p decision problem

歸約：A歸約到B痢甘，也就是說，我們對A套一個(gè)函數(shù)f茉贡，在f函數(shù)的作用下形成一個(gè)新的問題塞栅，對這個(gè)問題運(yùn)用B的黑盒解法，能夠解決問題A腔丧。

(B <=p A)一般說來放椰，B問題如果可以歸約到A問題，也就是說悔据，一個(gè)解決A問題的算法可以被用做子函數(shù)（子程序）來解決B問題庄敛，也就是說，求解B問題不會(huì)比求解A問題更困難科汗。因此，如果B問題是困難的绷雏，那么A問題也就是困難的头滔，因?yàn)椴淮嬖谇蠼釧問題的高效算法。(最后一句不懂)

我簡單說一下我理解的規(guī)約涎显，以X規(guī)約到Y(jié)為準(zhǔn)坤检，大概分成兩個(gè)方面：

1. X規(guī)約到Y(jié)，是說X問題能夠通過函數(shù) f 轉(zhuǎn)化成Y期吓，即如果Y是一個(gè)黑盒解法早歇，那么我對X的每一個(gè)實(shí)例通過 f 轉(zhuǎn)化成Y之后，都能用這個(gè)黑盒解出來讨勤，然后再把Y的答案轉(zhuǎn)回X的答案箭跳，一般來說漂彤，這個(gè)轉(zhuǎn)回在定義 f 的時(shí)候就有說明冠场。

2. 一般來說，做這個(gè)規(guī)約是為了解決問題X国旷，也就是說刨晴，在具體規(guī)約的時(shí)候屉来，①應(yīng)該對X的實(shí)例進(jìn)行刻畫路翻，肉眼找到答案，②然后對這個(gè)實(shí)例套上 f 形成新的實(shí)例茄靠，對新的實(shí)例套用Y的黑盒茂契，能夠找到步驟一中的答案。

注：在三的一些實(shí)例中細(xì)品慨绳。

二：算法思想

貪心

概念：在對問題求解時(shí)掉冶，總是做出在當(dāng)前看來是最好的選擇。

貪心的證明：先假設(shè)貪心算法得到的解不是最優(yōu)解儡蔓，假設(shè)S1是貪心算法得到的解郭蕉，而S2是所有最優(yōu)解中和S1具有最多相同元素的解，然后比較S1和S2喂江，觀察S1和S2中第一個(gè)（最前面一個(gè)）不一樣的元素召锈，然后在貪心解S2中將不一樣的元素?fù)Q成S1中的那個(gè)元素得到另一個(gè)最優(yōu)解S3，這樣S3和S1比S2和S1有更多相同元素获询，和假設(shè)S2是與S1有最多相同元素的最優(yōu)解矛盾涨岁，這樣來推導(dǎo)S1是最優(yōu)解。

我的理解：假設(shè)這個(gè)不是最優(yōu)的吉嚣，但是一定存在一個(gè)最優(yōu)的解在某一個(gè)位置之前和我當(dāng)前解結(jié)構(gòu)是一樣的梢薪，那么在這個(gè)位置，選最優(yōu)解也可以選當(dāng)前解尝哆，不影響最終答案秉撇。

[注]概念很簡單，但是實(shí)際操作的時(shí)候秋泄，貪心的角度很重要琐馆，同樣的貪心，方向?qū)α撕阈颍惴ň褪菍Φ摹?/p>

例子：

interval scheduling

給你一系列活動(dòng)瘦麸，每個(gè)活動(dòng)有一個(gè)起始時(shí)間和一個(gè)結(jié)束時(shí)間，要求在活動(dòng)不沖突的情況下找到一種有最多活動(dòng)的安排歧胁。

對于這個(gè)問題滋饲，我們有一下幾種貪心的角度：

①將任務(wù)按照開始時(shí)間升序排列。

②將任務(wù)按照結(jié)束時(shí)間升序排列喊巍。

③將任務(wù)按照任務(wù)時(shí)長升序排列屠缭。

④對于每一個(gè)任務(wù)，都記錄與其他任務(wù)沖突的數(shù)量玄糟，按照沖突數(shù)量的升序排列勿她。

其中1，3阵翎，4都是不可以的逢并。

任務(wù)結(jié)束時(shí)間的貪心證明（反證法）：

假設(shè)貪心不是最最優(yōu)的之剧，那我們在最優(yōu)解中找一個(gè)與當(dāng)前解有最相似的解。

由圖可以知道砍聊，貪心貪的就是最早結(jié)束背稼，所以如果不是最優(yōu)，那么最優(yōu)的結(jié)束時(shí)間一定晚于貪心的結(jié)束時(shí)間玻蝌。

由上圖就可以證明蟹肘。

網(wǎng)絡(luò)流

最大流通常與最小割相聯(lián)系。

f 為任意一個(gè)流俯树，cap為容量帘腹，對于任意的s-t割出來的點(diǎn)集（A，B）许饿，v( f ) <= cap(A, B)阳欲。

當(dāng)流增加到與割的容量相等時(shí)候，就不可能再有增長空間了陋率，稱為最大流球化。

對于割的容量來說，不同的割法會(huì)有不同流量瓦糟，有些割法永遠(yuǎn)不會(huì)有流達(dá)到筒愚，比如部分A = {s}, B = {V - s}，這種把源點(diǎn)割出來的割法菩浙。

綜上巢掺，通過這種感性的認(rèn)識，如果能找到一個(gè)最小的割劲蜻，那么這個(gè)割就一定是最大能跑到的流（如果流能更高的話在這個(gè)割上就會(huì)超過容量址遇，反證。）

上圖為一條增廣路斋竞，一條增廣路即為一條s-t的路徑，在路徑上仍有流可以跑秃殉，其曾廣的流就是該條路徑上最小的剩余容量坝初。（相當(dāng)于每找一條增廣路，就至少有一條邊達(dá)到滿流钾军。）

直到在圖中找不到增廣路鳄袍，此時(shí)已經(jīng)達(dá)到了最大流。

找ST集合：把滿流的邊去掉吏恭，從S出發(fā)走到能到的點(diǎn)拗小，遍歷的點(diǎn)就是S集合；剩下的點(diǎn)就屬于T集合樱哼。注意哀九，如果找到了在找S集合的時(shí)候找到了T點(diǎn)剿配，說明還可以繼續(xù)找增廣路。

[補(bǔ)]有一個(gè)很有趣的延伸阅束，如多源點(diǎn)多終點(diǎn)問題呼胚。問：如果我有兩個(gè)源點(diǎn)s1，s2息裸，兩個(gè)終點(diǎn)t1蝇更，t2，我想求一組流呼盆，使得s1-t1年扩，s2-t2的流達(dá)到最大，是否可以加一個(gè)源點(diǎn)S访圃，S與s1厨幻，s2相連，邊流無限大挽荠；加一個(gè)終點(diǎn)T克胳，T與t1，t2相連圈匆，邊流無限大漠另，然后這組ST的最大流即可≡咀——答案是No笆搓，無法保證是s1-t1，s2-t2纬傲，有可能交錯(cuò)满败。

動(dòng)態(tài)規(guī)劃和分治

例子講的感覺不是特別好，對理解感覺起不到很大作用叹括，希望以后有新的想法后進(jìn)行補(bǔ)充算墨。

三：算法的經(jīng)典問題

規(guī)約

規(guī)約是一個(gè)重要的概念和思想。

獨(dú)立集和點(diǎn)覆蓋：

一個(gè)圖的 最大獨(dú)立集 與 最小點(diǎn)覆蓋 是不相交的兩個(gè)點(diǎn)集汁雷，它們的并就是整個(gè)點(diǎn)集净嘀。

個(gè)人理解：獨(dú)立集和點(diǎn)覆蓋都是從點(diǎn)的角度進(jìn)行劃分的，如果我們從邊的角度來看侠讯，①一個(gè)最小的點(diǎn)覆蓋即為我集合中的每一個(gè)點(diǎn)都盡可能與更多的邊相連挖藏，②同時(shí)，一條邊的兩個(gè)端點(diǎn)中厢漩，只能有一個(gè)端點(diǎn)在最小點(diǎn)覆蓋中[下注]

[注]我們假設(shè)有一條邊兩個(gè)端點(diǎn)（u膜眠，v）都在點(diǎn)覆蓋之中，首先顯然u，v都不是端點(diǎn)宵膨，因?yàn)榧僭O(shè)u是端點(diǎn)的話只需要選擇v即可架谎；

集合覆蓋 <=p 點(diǎn)覆蓋

給一個(gè)集合S和一堆S的子集S1，S2柄驻，...狐树，Sm，問是否存在存在k個(gè)子集鸿脓，使它們的并集為S抑钟。

構(gòu)造：

集合為點(diǎn)，集合中的元素為邊野哭，有相同元素的邊相連在塔。（注意如果某一元素只在一個(gè)子集中出現(xiàn)，應(yīng)該怎么處理呢２η）

規(guī)約：在構(gòu)造的圖中找最小的點(diǎn)覆蓋蛔溃，選中的點(diǎn)能覆蓋所有的邊即為對應(yīng)集合的并集能包含所有的元素。所以就完成了集合覆蓋到點(diǎn)覆蓋的規(guī)約篱蝇。

3SAT <= 獨(dú)立集

構(gòu)造：每個(gè)句子構(gòu)造一個(gè)三角形贺待，把對應(yīng)變量但是相反取值的點(diǎn)相連。

規(guī)約：3SAT的有一個(gè)特點(diǎn)就是零截，每一個(gè)句子中至少有一個(gè)為真即可麸塞，每個(gè)句子都必須是真。將相同變量相反取值相連的目的就是涧衙，在最大獨(dú)立集中哪工，比如選擇x為真，則剩下所有句子中x-ba一定不會(huì)被選中弧哎，同時(shí)由獨(dú)立集和構(gòu)造出來三角形的性質(zhì)可以知道雁比，每一個(gè)句子，有且僅有一個(gè)會(huì)被選中（為真）撤嫩。如上圖偎捎，x1-ba為真，x2-ba和x3任選一個(gè)為真即可滿足序攘。

自規(guī)約

search problem <=p decision version

比如：如果能在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)哈密爾頓圈鸭限，那么就能在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)哈密爾頓圈（刪邊）

在此再談P和NP：

我們知道有些問題是可以從搜索問題規(guī)約到判斷問題的，也就是所該問題如果能在多項(xiàng)式內(nèi)判斷两踏，那么就能在多項(xiàng)式中搜索到，那么我們只需要說兜喻，這個(gè)判斷問題能在多項(xiàng)式時(shí)間內(nèi)求解梦染，就叫做P問題，也就是上圖紅字的意思；那NP問題呢帕识，必須要給出一個(gè)解的實(shí)例泛粹，判斷的是這個(gè)實(shí)例是否滿足求解問題，這個(gè)才是上圖中的紅字肮疗。比如晶姊，我如果能在多項(xiàng)式時(shí)間內(nèi)判斷哈密爾頓圈是否（Yes/No）存在，那這個(gè)就是ploy-time algorithm伪货，如果我給出了一系列點(diǎn)们衙，能過多項(xiàng)式時(shí)間內(nèi)判斷這些點(diǎn)能否構(gòu)成哈密爾頓圈，那這個(gè)就是poly-time certifier碱呼。

有向哈密爾頓圈規(guī)約到無向哈密爾頓圈

構(gòu)造：把一個(gè)點(diǎn)拆分成三個(gè)點(diǎn)蒙挑。

3SAT規(guī)約到有向哈密爾頓圈

構(gòu)造：（下面兩個(gè)圖要連在一起看）

從行的角度看，一行代表一個(gè)變量愚臀；從列的角度來看忆蚀，每三列代表一個(gè)句子。兩邊中一邊是兩個(gè)點(diǎn)姑裂，一邊是一個(gè)點(diǎn)馋袜，所以有k個(gè)句子的話，每一行有3k+3個(gè)節(jié)點(diǎn)舶斧。從哈密爾頓圈的答案轉(zhuǎn)到3SAT的答案看這個(gè)圈在每一行是從左到右還是從右到左欣鳖。

3SAT規(guī)約到子集和問題

子集和問題：給一個(gè)集合S，問是否能在集合中選取元素捧毛，使得總和為W观堂。

構(gòu)造：如下圖，按照前六行和前三列進(jìn)行分割呀忧，可以分成4部分师痕，其中1,3,4部分是固定的，即在第一部分而账，變量v列和 變量為v（包括變量及取反）的行對應(yīng)的格子為0胰坟，其余為0；第三部分全為0泞辐；第四部分按照12依次寫下來笔横。第二部分，如果Ci句子中有變量v咐吼，則記為1吹缔，因?yàn)橐粋€(gè)句子只有三個(gè)變量，可以簡單通過第二部分每一列和為3進(jìn)行判定锯茄。此時(shí)集合已經(jīng)構(gòu)造出來厢塘，W為111444茶没，與上面的規(guī)約相似，可以通過3SAT的簡單性質(zhì)進(jìn)行感性的認(rèn)知晚碾。

近似

近似的想法很簡單抓半，要解決一個(gè)問題，我們希望能夠做到①求解結(jié)果是最優(yōu)的 ②在多項(xiàng)式時(shí)間內(nèi)解決 ③對于任意的實(shí)例都能夠通過該算法解決「襦遥現(xiàn)在對于部分問題笛求，無法完全滿足以上要求，所以就犧牲了①糕簿，但是我們希望結(jié)果不是盲目的探入，所以就引入了近似的概念。

近似算法冶伞。比如2-近似新症，認(rèn)為W為近似解，W為最優(yōu)解响禽，在求最小值的情況下W<=2W徒爹；在求最大值的情況下，W>=1/2W*

負(fù)載均衡問題

給m個(gè)機(jī)器和n個(gè)任務(wù)芋类，每個(gè)任務(wù)有一個(gè)ti的執(zhí)行時(shí)間隆嗅，我們認(rèn)為完成最后一個(gè)任務(wù)所需的時(shí)間為負(fù)載時(shí)間，希望能夠讓這個(gè)負(fù)載時(shí)間最短侯繁。

第一種：將任務(wù)依次放在機(jī)器上胖喳，當(dāng)某個(gè)機(jī)器空閑時(shí)立即放入新任務(wù)。此時(shí)是2近似的贮竟。

證明：

引理1.最短時(shí)間安排是大于等于任務(wù)中時(shí)間最長的任務(wù)丽焊，L* >= max tj

我們在考慮放入最后一個(gè)任務(wù)前咕别，根據(jù)我們放置的規(guī)則技健，該機(jī)器是耗時(shí)最短，也就是說惰拱，該機(jī)器此時(shí)的用時(shí)是低于除掉最后一個(gè)任務(wù)后的平均時(shí)長雌贱，更低于所有任務(wù)的平均時(shí)長（引理2）；再根據(jù)引理1偿短，最后一個(gè)任務(wù)應(yīng)該是小于最優(yōu)解的欣孤。

補(bǔ)充：

在這里，我還想討論一下這個(gè)近似算法的中等于符號昔逗，先上結(jié)論：等號不一定能夠找到一個(gè)實(shí)例降传，但是可以構(gòu)造出一種結(jié)構(gòu)，通過取極限求得勾怒，我們認(rèn)為這樣 也算是緊的搬瑰。

構(gòu)造實(shí)例：有m個(gè)機(jī)器款票，其中m(m-1)個(gè)任務(wù)的用時(shí)為1，1個(gè)任務(wù)的用時(shí)為m泽论。肯定有一種任務(wù)集合卡乾，可以按照以下方式進(jìn)行安排翼悴，此時(shí)的貪心解為19。

此時(shí)最佳的解為10幔妨，如下圖：

通過推廣可以知道此時(shí)的比為（2m-1）/m鹦赎，當(dāng)m取極限，能夠達(dá)到2倍误堡。

第二種：將任務(wù)從大到小排序古话，然后依次放在機(jī)器上，當(dāng)某個(gè)機(jī)器空閑時(shí)立即放入新任務(wù)锁施。此時(shí)是2近似的陪踩。

引理3：如果有大于m個(gè)任務(wù)，那么L*>=2t(m-1)悉抵。證明：t(m+1)是目前最短的任務(wù)肩狂，且目前所有機(jī)器上都有任務(wù)了，所以該任務(wù)加入時(shí)最優(yōu)的情況不過是加入設(shè)備的原有任務(wù)剛好和t(m+1)相等姥饰，即等號傻谁。

中心點(diǎn)選取

（2近似）在n個(gè)點(diǎn)中，選取k個(gè)中心點(diǎn)列粪，使得這些中心點(diǎn)能夠以半徑R的圓包含所有的點(diǎn)审磁，讓其中最大的半徑最小，如下圖所示：

基礎(chǔ)：距離需要滿足的三個(gè)定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)

r(C)為C集合中所有點(diǎn)的最大覆蓋半徑岂座。（需要求min r(C)）

算法：在點(diǎn)集中任選一個(gè)作為中心點(diǎn)态蒂，然后重復(fù)以下步驟k-1次:選取距離已選點(diǎn)集中最遠(yuǎn)的點(diǎn)，加入點(diǎn)集掺逼。

證明：先假設(shè)r(C)< 1/2 * r(C)以選好的點(diǎn)畫半徑為1/2 * r(C)的圓吃媒，顯然可知[注]，這個(gè)圓里有且僅有一個(gè)r(C)中的點(diǎn)吕喘。那么根據(jù)在下圖中赘那，根據(jù)三角不等式可以得出：

[注]在每個(gè)點(diǎn)上r(c)一定會(huì)包含到c點(diǎn)，而r(C)<1/2 * r(C)氯质，相當(dāng)于大圓套小圓募舟，所以c*一定在c的圓中。

帶權(quán)最小點(diǎn)覆蓋——pricing method

（2近似）問題還是很好理解的闻察，在點(diǎn)上加權(quán)值拱礁，要找一個(gè)點(diǎn)覆蓋琢锋，使得權(quán)值最小。如下圖左邊就是一個(gè)帶權(quán)的最小點(diǎn)覆蓋呢灶。

算法： 任選一條邊(i, j)加上代價(jià)吴超，這個(gè)代價(jià)從零開始，且這個(gè)代價(jià)的最大值低于i和j節(jié)點(diǎn)的權(quán)值鸯乃。顯然鲸阻，這個(gè)邊權(quán)值的最大值取決于兩個(gè)端點(diǎn)權(quán)值的最小值，我們認(rèn)為當(dāng)邊權(quán)值與點(diǎn)權(quán)值相等時(shí)缨睡，對應(yīng)的那個(gè)點(diǎn)是緊的鸟悴。把所有緊的點(diǎn)找出來即為點(diǎn)覆蓋。

流程：

證明：

引理：邊權(quán)之和小于等于點(diǎn)覆蓋的點(diǎn)權(quán)之和奖年。這主要是由于涉及到一條邊上兩個(gè)點(diǎn)都被選（緊的）的情況细诸，感性認(rèn)知可以看上圖，縮放證明如下：

w(S)是等于所選的節(jié)點(diǎn)的權(quán)值之和的陋守，等于所選節(jié)點(diǎn)節(jié)點(diǎn)所對應(yīng)的邊權(quán)之和震贵，可以把它放大到所有節(jié)點(diǎn)對應(yīng)邊權(quán)之和，這樣因?yàn)橐粭l邊(u, v)在u上算過一次后還要在v上算一次嗅义，所以等于邊權(quán)和的兩倍屏歹。再由上面引理可得。

帶權(quán)最小點(diǎn)覆蓋——線性解法

主要為了線性規(guī)劃和整數(shù)規(guī)劃之碗。

（2近似）沒啥好說的蝙眶，只需要把方程構(gòu)造出來就行了。

由于求解出來結(jié)果不一定是整數(shù)褪那，所以我們認(rèn)為某一點(diǎn)的值大于1/2幽纷，就選入點(diǎn)集。

證明：

因?yàn)閤i+xj >=1,且都是正數(shù)博敬，那必至少一個(gè)點(diǎn)是大于1/2的（反證友浸，兩個(gè)都小于1/2則和小于1）。

背包問題

給你n個(gè)物品和一個(gè)背包偏窝，每個(gè)物品有一個(gè)價(jià)值v和一個(gè)大小w收恢，背包的容量是W，要求讓背包裝下盡可能大價(jià)值祭往。

背包的時(shí)間復(fù)雜度：O(nW)

注意其中n表示物品的個(gè)數(shù)伦意，無論是1個(gè)還是999個(gè)，他都是多項(xiàng)式的硼补，這個(gè)很好理解驮肉。但是W就不一樣了，這是一個(gè)數(shù)字已骇。我理解的是這個(gè)數(shù)字會(huì)很奇特离钝，比如1.00001票编，比如99999，這些有可能看起來不大但是實(shí)際在處理的時(shí)候很難處理的數(shù)字卵渴，統(tǒng)一的來說慧域，如果我們把這些數(shù)字放在電腦上，都會(huì)以二進(jìn)制的方式存儲(chǔ)起來浪读，有些數(shù)字用十進(jìn)制表示很小吊趾，但是放在二進(jìn)制上面就會(huì)很大，由W導(dǎo)致不能在多項(xiàng)式時(shí)間內(nèi)解決（找不到一個(gè)范圍/上界來框它）瑟啃。

算法： 為了處理這個(gè)問題，我們改動(dòng)了dp的狀態(tài)轉(zhuǎn)移方程揩尸，要讓這個(gè)轉(zhuǎn)移方程和W無關(guān)[注]蛹屿。

此時(shí)還不是多項(xiàng)式的，然后我們再對value進(jìn)行約岩榆。[注]

[注]這兩步中错负，我們把w改成v，并對v進(jìn)行近似處理勇边。OPT的含義變成了犹撒，在面對是否選擇第i個(gè)物品時(shí)，要想讓價(jià)值達(dá)到當(dāng)前值粒褒，最少的weight识颊。理由是更改后的誤差是可以忍受的：對v進(jìn)行近似，結(jié)果只會(huì)出現(xiàn)最大價(jià)值的上下誤差奕坟，如果對w進(jìn)行近似祥款，則有可能出現(xiàn)該物品不能放入背包中，導(dǎo)致整個(gè)物品直接放棄的情況月杉。