教學(xué)的至高境界 分級(jí)教學(xué)

Java工程師的工資待遇怎么樣?

Java工程師的工資待遇怎么樣?

Java軟件工程師一般月薪范圍在4000-10000元，遠(yuǎn)遠(yuǎn)超過了應(yīng)屆畢業(yè)生月薪 2500元的平均水平。通常來(lái)說，有一年工作經(jīng)驗(yàn)的Java高級(jí)軟件工程師的薪酬大致在年薪10—13萬(wàn)左右。

從Java的應(yīng)用領(lǐng)域來(lái)分，Java語(yǔ)言的應(yīng)用方向主要表現(xiàn)在以下三個(gè)方面：首 先是大中型的商業(yè)應(yīng)用;其次是桌面應(yīng)用，就是常說的C/S應(yīng)用;再次是移動(dòng)領(lǐng)域應(yīng)用。

綜上而言JAVA就業(yè)方向?yàn)椋嚎梢詮氖翵SP網(wǎng)站開發(fā)、Java編程、Java游戲開 發(fā)、Java桌面程序設(shè)計(jì)，以及其他與Java語(yǔ)言編程相關(guān)的工作?？蛇M(jìn)入電信、銀行、保險(xiǎn)專業(yè)軟件開發(fā)公司等從事軟件設(shè)計(jì)和開發(fā)工作。

Java基礎(chǔ)語(yǔ)法

Java基礎(chǔ)語(yǔ)法

Java基礎(chǔ)語(yǔ)法

流程控制語(yǔ)句

Java 編譯器執(zhí)行流程

if 分支結(jié)構(gòu)

switch 選擇結(jié)構(gòu)與相關(guān)規(guī)則

循環(huán)結(jié)構(gòu)

for 循環(huán)

while 循環(huán)

do-while 循環(huán)語(yǔ)句

各語(yǔ)句性能對(duì)比與應(yīng)用場(chǎng)景

特殊流程控制語(yǔ)句

方法的聲明與使用

方法調(diào)用的過程分析

跨類調(diào)用方法

參數(shù)的值傳遞

方法的重載 Overload

01分?jǐn)?shù)規(guī)劃問題相關(guān)算法與題目講解（二分法與Dinkelbach算法）

---

>

01分?jǐn)?shù)規(guī)劃算法 信息學(xué)競(jìng)賽 OI ACM 二分 Dinkelbach **優(yōu)比率生成樹 **優(yōu)比率環(huán)

---

01分?jǐn)?shù)規(guī)劃

張?zhí)煜?

blog.csdn.net/hzoi_ztxztx97@QQ.com

---

前置技能

二分思想 **短路算法 一些數(shù)學(xué)腦細(xì)胞？

---

問題模型1

基本01分?jǐn)?shù)規(guī)劃問題

給定n $n個(gè)二元組<nobr>(valuei,costi)</nobr> <script type="math/tex" id="MathJax-Element-2">(value_i,cost_i)，<nobr>valuei</nobr> <script type="math/tex" id="MathJax-Element-3">value_i是選擇此二元組獲得的價(jià)值（非負(fù)），<nobr>costi</nobr> <script type="math/tex" id="MathJax-Element-4">cost_i是選擇此二元組付出的代價(jià)（非負(fù)），設(shè)<nobr>xi(xi∈{0,1})</nobr> <script type="math/tex" id="MathJax-Element-5">x_i(x_i\in \{0,1\})代表第<nobr>i</nobr> <script type="math/tex" id="MathJax-Element-6">i個(gè)二元組的選與不選，**大(小)化下式 <nobr>maximize(or&nbsp;minimize)&nbsp;&nbsp;&nbsp;r=∑valuei?xi∑costi?xi</nobr> <script type="math/tex; mode=display" id="MathJax-Element-7"> maximize(or\ minimize)\ \ \ r = \frac{\sum value_i \cdot x_i}{\sum cost_i\cdot x_i} </p> <h3 id="解決方法"> <strong>解決方法</strong> </h3> <h4 id="二分法"> <strong>二分法</strong> </h4> <p> 設(shè)<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-8">r**大值為<nobr>r?</nobr> <script type="math/tex" id="MathJax-Element-9">r^*， <nobr>r?=∑valuei?xi∑costi?xi</nobr> <script type="math/tex; mode=display" id="MathJax-Element-10"> r^* = \frac{\sum value_i \cdot x_i}{\sum cost_i\cdot x_i} </p> <p> <nobr>∑valuei?xi?r??∑costi?xi=0</nobr> <script type="math/tex; mode=display" id="MathJax-Element-11"> \sum value_i \cdot x_i - r^*\cdot \sum cost_i\cdot x_i = 0 </p> <p> 設(shè)一個(gè)函數(shù)，自變量為<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-12">r值， <nobr>f(r)=∑valuei?xi?r??∑costi?xi</nobr> <script type="math/tex; mode=display" id="MathJax-Element-13"> f(r) =\sum value_i \cdot x_i - r^*\cdot \sum cost_i\cdot x_i </p> <p> 觀察這個(gè)函數(shù)，假如<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-14">\{x_i\}固定，則這個(gè)函數(shù)就是坐標(biāo)系中一條直線(<nobr>y=B?A?x</nobr> <script type="math/tex" id="MathJax-Element-15">y = B - A\cdot x)，每一組<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-16">\{x_i\}對(duì)應(yīng)著一條直線，這些直線斜率非正(因?yàn)?nobr>?A=?∑costi?xi≤0</nobr> <script type="math/tex" id="MathJax-Element-17">-A =- \sum cost_i\cdot x_i \le 0)，縱截距非負(fù)(因?yàn)?nobr>B=∑valuei?xi≥0</nobr> <script type="math/tex" id="MathJax-Element-18">B =\sum value_i \cdot x_i \ge 0 )，如圖1。 對(duì)于每一條直線，當(dāng)<nobr>f(r)=0</nobr> <script type="math/tex" id="MathJax-Element-19">f(r)=0時(shí)，橫截距就是這一組的<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-20">r，那么<nobr>r?</nobr> <script type="math/tex" id="MathJax-Element-21">r^*就是每條直線橫截距的**大值（每組<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-22">\{x_i\}對(duì)應(yīng)<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-23">r的**大值）如圖2。 在圖中上任取一條垂直<nobr>x</nobr> <script type="math/tex" id="MathJax-Element-24">x軸的豎線， 如果存在直線與這條豎線的交點(diǎn)縱坐標(biāo)為正，那么**優(yōu)值一定在當(dāng)前豎線的右側(cè)； 如果所有直線與這條豎線交點(diǎn)縱坐標(biāo)為負(fù)，那么**優(yōu)值一定在當(dāng)前豎線的左側(cè)； 如果所有直線與這條豎線交點(diǎn)縱坐標(biāo)非正且存在直線與這條豎線交點(diǎn)縱坐標(biāo)為0，那么當(dāng)前豎線橫坐標(biāo)即為**優(yōu)值<nobr>r?</nobr> <script type="math/tex" id="MathJax-Element-25">r^*。 按照這個(gè)思想，可以二分答案<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-26">r，那么二分時(shí)如何進(jìn)行判斷呢？ </p> <p> 選擇一個(gè)<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-27">r時(shí)需要判斷所有<nobr>f(r)</nobr> <script type="math/tex" id="MathJax-Element-28">f(r)的**大值是否為0，如果<nobr>max{f(r)}&gt;0</nobr> <script type="math/tex" id="MathJax-Element-29">max\{f(r)\} > 0則<nobr>r&lt;r?</nobr> <script type="math/tex" id="MathJax-Element-30">r < r^*；如果<nobr>max{f(r)}&lt;0</nobr> <script type="math/tex" id="MathJax-Element-31">max\{f(r)\} < 0 則 <nobr>r&gt;r?</nobr> <script type="math/tex" id="MathJax-Element-32">r > r*。 怎樣求<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-33">max\{f(r)\}? <nobr>f(r)=∑valuei?xi?r?∑costi?xi=∑(valuei?r?costi)?xi</nobr> <script type="math/tex; mode=display" id="MathJax-Element-34"> \begin{aligned} f(r) &= \sum value_i \cdot x_i - r \cdot \sum cost_i\cdot x_i \\ &= \sum (value_i-r\cdot cost_i) \cdot x_i \end{aligned} </p> <p> 二分一個(gè)<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-35">r時(shí)，每個(gè)二元組的<nobr>valuei?r?costi</nobr> <script type="math/tex" id="MathJax-Element-36">value_i-r\cdot cost_i 都可以求出，設(shè)其為<nobr>weighti</nobr> <script type="math/tex" id="MathJax-Element-37">weight_i，現(xiàn)在的目標(biāo)就是找到一組<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-38">\{x_i\}使得<nobr>∑wighti?xi</nobr> <script type="math/tex" id="MathJax-Element-39">\sum wight_i\cdot x_i**大（即求<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-40">max\{f(r)\}）。怎么找到這一組<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-41">\{x_i\}，或者直接求得<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-42">max\{f(r)\}呢？具體問題具體分析，經(jīng)常借助**短路算法判斷是否存在負(fù)環(huán)。下面會(huì)有幾道例題。 </p> <p> 01分?jǐn)?shù)規(guī)劃還會(huì)與其他問題結(jié)合，如網(wǎng)絡(luò)流等。 </p> <h4 id="dinkelbach算法"> <strong><nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-43">Dinkelbach算法</strong> </h4> <p> 這個(gè)算法我是在寫這篇文章時(shí)才知道的。 </p> <p> 思考上述二分算法的思路，設(shè)二分過程中某一個(gè)二分值為<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-44">r，二分時(shí)的判斷條件是<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-45">max\{f(r)\}的正負(fù)性，而這個(gè)<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-46">r除了讓<nobr>L</nobr> <script type="math/tex" id="MathJax-Element-47">L右移或者<nobr>R</nobr> <script type="math/tex" id="MathJax-Element-48">R左移就沒有用了?，F(xiàn)在思考某一過程中<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-49">r與<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-50">max\{f(r)\}能否再被利用。 二分時(shí)，假如<nobr>max{f(r)}&gt;0</nobr> <script type="math/tex" id="MathJax-Element-51">max\{f(r)\}>0這說明**優(yōu)解在當(dāng)前<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-52">r的右側(cè)，于是讓<nobr>L=r</nobr> <script type="math/tex" id="MathJax-Element-53">L=r，但是，如果將<nobr>L</nobr> <script type="math/tex" id="MathJax-Element-54">L移動(dòng)到<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-55">max\{f(r)\}對(duì)應(yīng)直線的橫截距呢？顯然，算法會(huì)變得更快。這個(gè)思想就是<nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-56">Dinkelbach算法的內(nèi)涵。 <nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-57">Dinkelbach實(shí)質(zhì)上是一種迭代算法，基于這樣的思想：不去二分答案，而是先隨便給定一個(gè)答案，然后根據(jù)更優(yōu)的解（<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-58">max\{f(r)\}對(duì)應(yīng)直線的橫截距）不斷移動(dòng)答案，逼近**優(yōu)解。理論上它比二分快些。 在這個(gè)算法中，一般將<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-59">r初始化為<nobr>0</nobr> <script type="math/tex" id="MathJax-Element-60">0。 </p> <h4 id="兩種算法的比較"> <strong>兩種算法的比較</strong> </h4> <p> <nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-61">Dinkelbach算法的弊端就是需要保存解。這兩個(gè)算法解決統(tǒng)一問題實(shí)際上都有可能快些。 我覺著我一般還是用二分。。。。 </p> <h3 id="例題"> <strong>例題</strong> </h3> <h1 id="只先寫了文章還差相關(guān)題目的分析代碼等得等個(gè)一兩天再2017-02-06留"> 只先寫了文章，還差相關(guān)題目的分析，代碼等。得等個(gè)一兩天再。2017-02-06留。 </h1> <p> Poj2976Dropping tests </p> <hr /> <h1 id="問題模型2"> <strong>問題模型2</strong> </h1> <h3 id="**優(yōu)比率生成樹"> <strong>**優(yōu)比率生成樹</strong> </h3> <p> 帶權(quán)無(wú)向圖<nobr>G</nobr> <script type="math/tex" id="MathJax-Element-62">G， 對(duì)于圖中每條邊<nobr>ei</nobr> <script type="math/tex" id="MathJax-Element-63">e_i， 都有<nobr>valuei</nobr> <script type="math/tex" id="MathJax-Element-64">value_i和<nobr>costi</nobr> <script type="math/tex" id="MathJax-Element-65">cost_i，現(xiàn)在求一棵生成樹<nobr>T</nobr> <script type="math/tex" id="MathJax-Element-66">T，**大（?。┗?nobr>∑valuei∑costi,ei∈T</nobr> <script type="math/tex" id="MathJax-Element-67">\frac{\sum value_i}{\sum cost_i},e_i\in T </p> <h3 id="解決方法-1"> <strong>解決方法</strong> </h3> <p> 套用01分?jǐn)?shù)規(guī)劃模型，如果<nobr>ei∈T</nobr> <script type="math/tex" id="MathJax-Element-68">e_i\in T則<nobr>xi=1</nobr> <script type="math/tex" id="MathJax-Element-69">x_i=1否則<nobr>xi=0</nobr> <script type="math/tex" id="MathJax-Element-70">x_i=0。 </p> <h4 id="二分法-1"> <strong>二分法</strong> </h4> <p> 二分答案<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-71">r，邊賦值<nobr>weighti=valuei?r?costi</nobr> <script type="math/tex" id="MathJax-Element-72">weight_i = value_i-r\cdot cost_i，因?yàn)槭巧蓸?，邊的?shù)量確定，那么<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-73">max\{f(r)\}需要選取前<nobr>|G|?1</nobr> <script type="math/tex" id="MathJax-Element-74">|G|-1大的<nobr>weighti</nobr> <script type="math/tex" id="MathJax-Element-75">weight_i，也就是求**大生成樹，按**大生成樹權(quán)值的正負(fù)性就可以二分了。 </p> <h4 id="dinkelbach算法-1"> <strong><nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-76">Dinkelbach算法</strong> </h4> <p> 當(dāng)前答案<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-77">r，邊賦值<nobr>weighti=valuei?r?costi</nobr> <script type="math/tex" id="MathJax-Element-78">weight_i = value_i-r\cdot cost_i，同樣求**大生成樹，找到<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-79">max \{f(r)\}對(duì)應(yīng)的邊集<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-80">\{x_i\}，也就是**大生成樹的邊集。對(duì)這個(gè)邊集找橫截距當(dāng)做下一次答案。橫截距是啥呢？ <nobr>f(r)=B?A?rrr=0=B/A=∑valuei?xi∑costi?xi</nobr> <script type="math/tex; mode=display" id="MathJax-Element-81"> \begin{aligned} f(r)=B-A\cdot r &= 0 \\ r&=B/A \r &=\frac{\sum value_i \cdot x_i}{ \sum cost_i\cdot x_i} \end{aligned} </p> <h3 id="例題-1"> <strong>例題</strong> </h3> <p> poj2728Desert King(**優(yōu)比率生成樹) </p> <hr /> <h1 id="問題模型3"> <strong>問題模型3</strong> </h1> <h3 id="**優(yōu)比率環(huán)"> <strong>**優(yōu)比率環(huán)</strong> </h3> <p> 給定有點(diǎn)權(quán)和邊權(quán)的圖，求一個(gè)環(huán)，使得環(huán)的點(diǎn)權(quán)和與邊權(quán)和的比值**大。 </p> <h3 id="解決方法-2"> <strong>解決方法</strong> </h3> <p> 套用01分?jǐn)?shù)規(guī)劃模型，點(diǎn)權(quán)為<nobr>valuei</nobr> <script type="math/tex" id="MathJax-Element-82">value_i，邊權(quán)為<nobr>costi</nobr> <script type="math/tex" id="MathJax-Element-83">cost_i，一個(gè)環(huán)為<nobr>C</nobr> <script type="math/tex" id="MathJax-Element-84">C 問題要求**大化<nobr>∑valuei∑costi,(i∈C)</nobr> <script type="math/tex" id="MathJax-Element-85">\frac{\sum value_i }{\sum cost_i},(i\in C) 邊數(shù)和點(diǎn)數(shù)是相同的，但上述式子表述不是很正確，意會(huì)即可。 若答案為<nobr>r?</nobr> <script type="math/tex" id="MathJax-Element-86">r^*，那么任意一個(gè)環(huán) <nobr>∑valuei∑costi∑valueir??∑costi?∑valuei≤r?≤r??∑costi≥0</nobr> <script type="math/tex; mode=display" id="MathJax-Element-87"> \begin{aligned} \frac{\sum value_i }{\sum cost_i}&\le r^* \\sum value_i&\le r^*\cdot \sum cost_i \r^*\cdot \sum cost_i -\sum value_i &\ge 0 \end{aligned} </p> <h4 id="二分法-2"> <strong>二分法</strong> </h4> <p> 設(shè)當(dāng)前答案<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-88">r， <nobr>r&lt;r?</nobr> <script type="math/tex" id="MathJax-Element-89">r < r^*，至少存在一個(gè)環(huán)，<nobr>r?∑costi?∑valuei&lt;0</nobr> <script type="math/tex" id="MathJax-Element-90">r \cdot \sum cost_i -\sum value_i < 0，即存在負(fù)權(quán)回路（將邊權(quán)設(shè)為<nobr>r?costi?valuei</nobr> <script type="math/tex" id="MathJax-Element-91">r\cdot cost_i-value_i，不是提前算出，而是在更新路徑的時(shí)候從哪個(gè)點(diǎn)訪問到這條邊的就將這條邊設(shè)為相應(yīng)點(diǎn)權(quán)與邊權(quán)的對(duì)應(yīng)值）； <nobr>r≥r?</nobr> <script type="math/tex" id="MathJax-Element-92">r\ge r^*，則不存在負(fù)環(huán)。 </p> <p> 求負(fù)環(huán)可以用Bellman-Ford，但是比較慢，一般用spfa算法求負(fù)環(huán) 具體判斷方法為，一個(gè)點(diǎn)不能入隊(duì)<nobr>n</nobr> <script type="math/tex" id="MathJax-Element-93">n次，否則有負(fù)環(huán)；一條**短路徑長(zhǎng)度不能到<nobr>n</nobr> <script type="math/tex" id="MathJax-Element-94">n，否則有負(fù)環(huán)。兩個(gè)判斷方法可以同時(shí)使用。 </p> <h4 id="dinkelbach算法-2"> <strong><nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-95">Dinkelbach算法</strong> </h4> <p> 如果用這個(gè)算法需要記錄下來(lái)一個(gè)負(fù)環(huán)，實(shí)現(xiàn)還是能實(shí)現(xiàn)的，但是沒有二分 spfa好寫。 </p> <h3 id="例題-2"> <strong>例題</strong> </h3> <p> poj 3621(**優(yōu)比率環(huán)) </p> <h1 id="問題模型4"> <strong>問題模型4</strong> </h1> <h3 id="**大密度子圖"> <strong>**大密度子圖</strong> </h3> <p> 這個(gè)問題會(huì)寫在網(wǎng)絡(luò)流總結(jié)中。 </p> <hr /> <h1 id="參考資料"> <strong>參考資料</strong> </h1> <p> 【1】KirisameMarisa - NYIST 914Yougth的**大化【二分搜索/Dinkelbach算法】 【2】PerSeAwe - ［Algorithm］01分?jǐn)?shù)規(guī)劃 </p> </p> <p> <b>相關(guān)推薦：</b> </p> <hr /> <p> <a href="http://m.k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)</a>&nbsp; &nbsp;<a href="http://m.k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)班</a>&nbsp; &nbsp;<a href="http://m.k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)機(jī)構(gòu)</a> </p>$