教学的至高境界分级教学

昆山培训靠谱吗

Java工程师的工资待遇怎么样?

昆山培训靠谱吗

Java工程师的工资待遇怎么样?

Java软件工程师一般月薪范围在4000-10000元，远远超过了应届毕业生月薪 2500元的平均水平。通常来说，有一年工作经验的Java高级软件工程师的薪酬大致在年薪10—13万左右。

从Java的应用领域来分，Java语言的应用方向主要表现在以下三个方面：首先是大中型的商业应用;其次是桌面应用，就是常说的C/S应用;再次是移动领域应用。

综上而言JAVA就业方向为：可以从事JSP网站开发、Java编程、Java游戏开发、Java桌面程序设计，以及其他与Java语言编程相关的工作。可进入电信、银行、保险专业软件开发公司等从事软件设计和开发工作。

Java基础语法

昆山培训靠谱吗

Java基础语法

Java基础语法

流程控制语句

Java 编译器执行流程

if 分支结构

switch 选择结构与相关规则

循环结构

for 循环

while 循环

do-while 循环语句

各语句性能对比与应用场景

特殊流程控制语句

方法的声明与使用

方法调用的过程分析

跨类调用方法

参数的值传递

方法的重载 Overload

01分数规划问题相关算法与题目讲解（二分法与Dinkelbach算法）

01分数规划算法信息学竞赛 OI ACM 二分 Dinkelbach **优比率生成树 **优比率环

01分数规划

张天翔

blog.csdn.net/hzoi_ztxztx97@QQ.com

前置技能

二分思想 **短路算法一些数学脑细胞？

问题模型1

基本01分数规划问题

给定n $n个二元组<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是选择此二元组获得的价值（非负），<nobr>costi</nobr> <script type="math/tex" id="MathJax-Element-4">cost_i是选择此二元组付出的代价（非负），设<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个二元组的选与不选，**大(小)化下式 <nobr>maximize(or minimize)   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> 设<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> 设一个函数，自变量为<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> 观察这个函数，假如<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-14">\{x_i\}固定，则这个函数就是坐标系中一条直线(<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\}对应着一条直线，这些直线斜率非正(因为<nobr>?A=?∑costi?xi≤0</nobr> <script type="math/tex" id="MathJax-Element-17">-A =- \sum cost_i\cdot x_i \le 0)，纵截距非负(因为<nobr>B=∑valuei?xi≥0</nobr> <script type="math/tex" id="MathJax-Element-18">B =\sum value_i \cdot x_i \ge 0 )，如图1。对于每一条直线，当<nobr>f(r)=0</nobr> <script type="math/tex" id="MathJax-Element-19">f(r)=0时，横截距就是这一组的<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\}对应<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轴的竖线，如果存在直线与这条竖线的交点纵坐标为正，那么**优值一定在当前竖线的右侧；如果所有直线与这条竖线交点纵坐标为负，那么**优值一定在当前竖线的左侧；如果所有直线与这条竖线交点纵坐标非正且存在直线与这条竖线交点纵坐标为0，那么当前竖线横坐标即为**优值<nobr>r?</nobr> <script type="math/tex" id="MathJax-Element-25">r^*。按照这个思想，可以二分答案<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-26">r，那么二分时如何进行判断呢？ </p> <p> 选择一个<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-27">r时需要判断所有<nobr>f(r)</nobr> <script type="math/tex" id="MathJax-Element-28">f(r)的**大值是否为0，如果<nobr>max{f(r)}>0</nobr> <script type="math/tex" id="MathJax-Element-29">max\{f(r)\} > 0则<nobr>r<r?</nobr> <script type="math/tex" id="MathJax-Element-30">r < r^*；如果<nobr>max{f(r)}<0</nobr> <script type="math/tex" id="MathJax-Element-31">max\{f(r)\} < 0 则 <nobr>r>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> 二分一个<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-35">r时，每个二元组的<nobr>valuei?r?costi</nobr> <script type="math/tex" id="MathJax-Element-36">value_i-r\cdot cost_i 都可以求出，设其为<nobr>weighti</nobr> <script type="math/tex" id="MathJax-Element-37">weight_i，现在的目标就是找到一组<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)\}呢？具体问题具体分析，经常借助**短路算法判断是否存在负环。下面会有几道例题。 </p> <p> 01分数规划还会与其他问题结合，如网络流等。 </p> <h4 id="dinkelbach算法"> <strong><nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-43">Dinkelbach算法</strong> </h4> <p> 这个算法我是在写这篇文章时才知道的。 </p> <p> 思考上述二分算法的思路，设二分过程中某一个二分值为<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-44">r，二分时的判断条件是<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-45">max\{f(r)\}的正负性，而这个<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左移就没有用了。现在思考某一过程中<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)\}能否再被利用。二分时，假如<nobr>max{f(r)}>0</nobr> <script type="math/tex" id="MathJax-Element-51">max\{f(r)\}>0这说明**优解在当前<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-52">r的右侧，于是让<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移动到<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-55">max\{f(r)\}对应直线的横截距呢？显然，算法会变得更快。这个思想就是<nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-56">Dinkelbach算法的内涵。 <nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-57">Dinkelbach实质上是一种迭代算法，基于这样的思想：不去二分答案，而是先随便给定一个答案，然后根据更优的解（<nobr>max{f(r)}</nobr> <script type="math/tex" id="MathJax-Element-58">max\{f(r)\}对应直线的横截距）不断移动答案，逼近**优解。理论上它比二分快些。在这个算法中，一般将<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算法的弊端就是需要保存解。这两个算法解决统一问题实际上都有可能快些。我觉着我一般还是用二分。。。。 </p> <h3 id="例题"> <strong>例题</strong> </h3> <h1 id="只先写了文章还差相关题目的分析代码等得等个一两天再2017-02-06留"> 只先写了文章，还差相关题目的分析，代码等。得等个一两天再。2017-02-06留。 </h1> <p> Poj2976Dropping tests </p> <hr /> <h1 id="问题模型2"> <strong>问题模型2</strong> </h1> <h3 id="**优比率生成树"> <strong>**优比率生成树</strong> </h3> <p> 带权无向图<nobr>G</nobr> <script type="math/tex" id="MathJax-Element-62">G，对于图中每条边<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，现在求一棵生成树<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分数规划模型，如果<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，因为是生成树，边的数量确定，那么<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，也就是求**大生成树，按**大生成树权值的正负性就可以二分了。 </p> <h4 id="dinkelbach算法-1"> <strong><nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-76">Dinkelbach算法</strong> </h4> <p> 当前答案<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)\}对应的边集<nobr>{xi}</nobr> <script type="math/tex" id="MathJax-Element-80">\{x_i\}，也就是**大生成树的边集。对这个边集找横截距当做下一次答案。横截距是啥呢？ <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(**优比率生成树) </p> <hr /> <h1 id="问题模型3"> <strong>问题模型3</strong> </h1> <h3 id="**优比率环"> <strong>**优比率环</strong> </h3> <p> 给定有点权和边权的图，求一个环，使得环的点权和与边权和的比值**大。 </p> <h3 id="解决方法-2"> <strong>解决方法</strong> </h3> <p> 套用01分数规划模型，点权为<nobr>valuei</nobr> <script type="math/tex" id="MathJax-Element-82">value_i，边权为<nobr>costi</nobr> <script type="math/tex" id="MathJax-Element-83">cost_i，一个环为<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) 边数和点数是相同的，但上述式子表述不是很正确，意会即可。若答案为<nobr>r?</nobr> <script type="math/tex" id="MathJax-Element-86">r^*，那么任意一个环 <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> 设当前答案<nobr>r</nobr> <script type="math/tex" id="MathJax-Element-88">r， <nobr>r<r?</nobr> <script type="math/tex" id="MathJax-Element-89">r < r^*，至少存在一个环，<nobr>r?∑costi?∑valuei<0</nobr> <script type="math/tex" id="MathJax-Element-90">r \cdot \sum cost_i -\sum value_i < 0，即存在负权回路（将边权设为<nobr>r?costi?valuei</nobr> <script type="math/tex" id="MathJax-Element-91">r\cdot cost_i-value_i，不是提前算出，而是在更新路径的时候从哪个点访问到这条边的就将这条边设为相应点权与边权的对应值）； <nobr>r≥r?</nobr> <script type="math/tex" id="MathJax-Element-92">r\ge r^*，则不存在负环。 </p> <p> 求负环可以用Bellman-Ford，但是比较慢，一般用spfa算法求负环具体判断方法为，一个点不能入队<nobr>n</nobr> <script type="math/tex" id="MathJax-Element-93">n次，否则有负环；一条**短路径长度不能到<nobr>n</nobr> <script type="math/tex" id="MathJax-Element-94">n，否则有负环。两个判断方法可以同时使用。 </p> <h4 id="dinkelbach算法-2"> <strong><nobr>Dinkelbach</nobr> <script type="math/tex" id="MathJax-Element-95">Dinkelbach算法</strong> </h4> <p> 如果用这个算法需要记录下来一个负环，实现还是能实现的，但是没有二分 spfa好写。 </p> <h3 id="例题-2"> <strong>例题</strong> </h3> <p> poj 3621(**优比率环) </p> <h1 id="问题模型4"> <strong>问题模型4</strong> </h1> <h3 id="**大密度子图"> <strong>**大密度子图</strong> </h3> <p> 这个问题会写在网络流总结中。 </p> <hr /> <h1 id="参考资料"> <strong>参考资料</strong> </h1> <p> 【1】KirisameMarisa - NYIST 914Yougth的**大化【二分搜索/Dinkelbach算法】【2】PerSeAwe - ［Algorithm］01分数规划 </p> </p> <p> <b>相关推荐：</b> </p> <hr /> <p> <a href="https://www.thea.cn/px189_jssz/" target="_blank">苏州JAVA培训</a>   <a href="https://www.thea.cn/px189_jssz/" target="_blank">苏州JAVA培训班</a>   <a href="https://www.thea.cn/px189_jssz/" target="_blank">苏州JAVA培训机构</a> </p>$