计算机科学导论-计算思维程序实践 课件 第13、14讲-从背包问题求解看算法-数学建模与不同算法策略、-什么是有限时间内能求解-问题的计算复杂性与分类

第13讲从背包问题求解看算法

—数学建模与不同算法策略哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣【示例】有1个背包，可装载重量最大15Kg；有5种物品，其重量和价值如图所示。问：如何装载物品，才能使该背包装载的物品总价值最大。一个示例问题基本的求解思维？【示例】有1个背包，可装载重量最大15Kg；有5种物品，其重量和价值如图所示。问：如何装载物品，才能使该背包装载的物品总价值最大。一个示例基本的求解思维—【枚举-计算-验证-优化】产生一种装载方案，并计算其装载物品价值装载1种物品有5种方案装载2种物品：从5种中取出2种的所有组合=10装载3种物品：从5种中取出3种的所有组合=10

装载4种物品：从5种中取出4种的所有组合=5

装载5种物品有1种方案产生所有装载方案，并从中选择出装载物品价值最大的方案，同时满足背包重量约束怎样表达装载方案?【一般性问题】有1个背包，可装载重量有限制。有n种物品，每种物品最多1件，且其重量和价值已知。怎样选择物品放入背包，才能使背包中物品价值最大？数学建模背包问题的数学建模

算法表达程序流程图的基本符号矩形框表示一组顺序执行的语句菱形框表示判断语句，决定下一步程序的走向圆形框表示程序的起始和结束带箭头的线段表示程序的走向开始第1条规则或语句第n条规则或语句结束顺序结构的流程图开始条件成立否？是否条件成立时执行的规则或语句结束条件不成立时执行的规则或语句分支结构的流程图算法表达算法的三种控制结构：顺序、分支、循环（有界循环和条件循环）初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句结束是否循环结束有界循环结构的流程图(循环次数确定)初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句结束否循环未结束是条件循环结构的流程图(循环次数不确定)要注意：循环结构不能无限循环，所以要有修改改变条件算法表达背包问题的求解算法【遍历算法】【当前物品组合S】设为空，【当前组合总价值SP】设为0开始所有物品组合完毕否？结束否是形成物品的一个新组合x,并计算该组合的物品总重量Wnew和物品总价值Pnew

比【当前组合总价值SP】大吗？将该组合x记录到【当前物品组合S】，并用其总价值Pnew更新【当前组合总价值SP】输出【当前物品组合S】及【当前组合总价值SP】是否物品总重量超过背包的总重限制W了吗？否是用数组的下标i表示物品i物品的一个组合表示为数组x，即：x[1]，…，x[n]。其中x[i]为0或1：为0表示不选择物品i，为1表示选择物品i物品i的重量存储在w[i]中，价值存储在p[i]中【当前物品组合S】与x一样的数组，S[1]，…，S[n]【当前组合总价值SP】为一数值型变量新组合，即产生一个不重复的x,j从1到n,依次给x[j]赋0和1。

如{0,0,0,0,0}{0,0,0,0,1}{0,0,0,1,0}{0,0,0,1,1}{0,0,1,0,0}

…物品总重量的计算：Wnew=

w[i]*x[i]fori=1,…,n。物品总价值的计算：Pnew=

p[i]*x[i]fori=1,…,n。IfWnew>WW为背包的总重限制IfPnew>SPSP

PnewS

x算法模拟背包问题求解-遍历策略【练习】x4x3x2x1时间复杂性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，通常评估算法基本步骤的执行次数来获得T(n)，它是n的某一函数，则T(n)称为这一算法的“时间复杂性”或“时间复杂度”。“大O记法”：基本参数n——问题实例的规模把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“≈”，如n2+n+1=Ο(n2)。空间复杂性：算法在执行过程中所占存储空间的大小。算法获得结果的时间有多长?算法复杂性O(f(n))算法复杂性算法的时间复杂性与空间复杂性算法优化背包问题的求解算法【遍历算法—优化】S设为空；SP=0开始所有物品组合完毕否？结束否是

Pnew>SP

S=x;SP=Pnew输出S和SP是否Wnew>W？否是S设为空；SP=0开始所有物品组合完毕否？结束否是

Pnew>SP

S=x;SP=Pnew输出S和SP是否Wnew>W？否是

Q：每个组合都要计算Pnew是否有必要？Q：这样是否比左侧算法更快呢？算法优化的目的是减少无效计算量！怎样产生和产生什么样的新组合？Q：组合次数为多少？2n算法复杂性=(n+n)2n=O(n*2n)

计算需要

循环n次贪心算法是一种算法策略。基本思想“今朝有酒今朝醉”，一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。一个物品一个物品地选择，直到背包装满为止。每次在选择下一个物品的时候，只考虑当前情况，保证迄今为止所做出的选择是最好的。算法的不同策略背包问题求解-贪心策略x4x3x2x1x5Q：贪心算法求得的解是最优解吗？不一定算法的不同策略背包问题求解-贪心策略【练习】x4x3x2x1x5价值高的物品优先重量小的物品优先性价比高的物品优先开始初始化重量数组w[]，价值数组p[];Pnew=0;Wnew=0;x[]=0;I=0;I<n?逐个输出x[]中的全部元素;输出Pnew;输出Wnew结束否从1号到N号物品的未被选中物品中选出重量最小者，假设其编号记为jWnew+w[j]>W?x[j]=1;Pnew=Pnew+p[j]；Wnew=Wnew+w[j]；I=I+1否x[k]==1?是是k=1w[k]<Wcur?否j=k;Wcur=w[k]是k=k+1k>n?是返回

j。当j=0时表示未找到任何物品。否则j为物品编号是否

j=0；

将Wcur设为一个大数；否j==0?是否开始结束算法表达背包问题的贪心算法求解（重量小的物品优先）子算法一重循环，故算法复杂性=O(n)

算法两重循环(含子算法)，故算法复杂性=O(n2)

不同的问题背包问题分类有n种物品，物品j的重量为wj，价格为pj,假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则为0-1背包问题如果限定物品j最多只能选择bj个，则为有界背包问题或多重背包问题

如果不限定每种物品的数量，则为无界背包问题或完全背包问题背包问题是一类重要的问题，研究者提出了很多算法，如贪心算法、动态规划算法等，同学可自主研究之。完成数学建模才能精准抓住应用问题的本质不同的应用问题，可能是相同的算法问题股票投资组合问题产品品种的组合问题背包问题（有界背包）有n种股票可供选择，每种股票j最多买bj股，怎样一个投资组合，才能使股票收益最大有n种产品可供销售，每种产品j最多可销售bj个，怎样一个产品组合，才能使产品销售价值最大有n种物品，每种物品j最多选择bj个，怎样选择物品放入背包，才能使背包中物品价值最大n种股票可用编号1,…,n表示每种股票j的价格为wj。每种股票j的收益为pj。可用于购买股票的资本为Wn种产品。可用编号1,…,n表示每种产品j的可销售数量为wj。每种产品j的价格为pj。市场可接受产品的总数量Wn种物品。可用编号1,…,n表示每种物品j的重量为wj。每种物品j的价值为pj。背包的总重量为W求一组合x=(x1,x2,..xj,..,xn)。其中股票j选择xj股。xj=0,…,bj为购买股数求一组合x=(x1,x2,..xj,..,xn)。其中产品j选择xj个。xj=0,…,bj为销售数量求一组合x=(x1,x2,..xj,..,xn)。其中物品j选择xj个。xj=0,…,bj为选择个数,其中xj=0,…,bj,其中xj=0,…,bj,其中xj=0,…,bjx要使得最大x要使得最大x要使得最大问题表述输入/已知输出/结果约束目标应用问题建模要素从背包问题求解看算法小结问题建模：输入【已知】，输出【可能解的形式】，约束【可行解的条件】，目标【最优解的条件】用自然数1…n表达现实的具体对象，具体对象的相关特征数据就可用带下标的变量表达，如第i个对象的特征就可用pi,ti等来表达（对应到算法/程序就是p[i],t[i]等）。通过自然数及其下标将不同类型的数据关联起来，是算法类问题抽象的重要方法。输出可用一个自然数序列来表示x=(x1,x2,…,xn)，此时的i表示为对象i，而xi则为对象i的某一特征值（典型的是0选择和1不选），在算法/程序中可用一维数组x[]来表达。这是表达可能解空间的典型形式。衡量算法的执行时间长短，可用算法复杂度来衡量。求解问题可有不同的算法策略，不同算法策略得到的解可能是不同的，算法复杂度也可能有很大的差异。算法研究的基础就是枚举-计算-验证，然后对算法做优化，主要目标是减少无效计算量。第14讲什么是有限时间内能求解

—问题的计算复杂性与分类哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣什么是有限时间内能求解的问题？什么是难解性问题？关于问题求解的疑问【疑问】算法复杂性算法复杂性的概念如何评价算法的性能?算法复杂性，是指求解一个问题的某一个算法的复杂性空间复杂性：衡量算法运行中所需要的存储空间（参照时间复杂性来进一步理解）时间复杂性：衡量算法的运行速度。一个算法由一些基本步骤构成，则算法基本步骤的执行次数被称为时间复杂性。问题通常与自然数n相关联，以反映问题的规模。例如求解5种、50种、50000种物品的组合问题，就是不同规模的问题。问题求解算法通常与问题规模n相关（典型的就是循环、递归等）。算法基本步骤的执行次数通常被表达为关于n的一个函数T(n)，该T(n)被称为时间复杂性或时间复杂度。例如T(n)=2n,或者T(n)=2n2+3n+5。时间复杂性是衡量算法的运行时间随着问题规模的增大而增加的趋势，而不是具体的运行时间。故而时间复杂性通常以量级来衡量，即大O表示法：O(T(n))。例如O(2n2+3n+5)=O(n2)，表示它们是同一量级的复杂性。算法复杂性算法复杂性计算示例S设为空；SP=0开始所有物品组合完毕否？结束否是

Pnew>SP

S=x;SP=Pnew输出S和SP是否Wnew>W？否是Q：组合次数为多少？2n每个组合：做n次乘法求Wnew做n次乘法求Pnew算法复杂性=(n+n+1+1+2+1)2n+3=(2n+5)2n+3=O(n*2n)问题规模n计算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

8000O(n3)O(3n)0.2秒4

1028秒=1015年注：每秒百万次，n=60，1015年相当于10亿台计算机计算一百万年O(n!)与O(n3)、O(n3)与O(3n)的差别O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(nb)算法复杂性不同量级复杂性在计算时间方面的差异算法复杂性不同量级复杂性在计算时间方面的差异算法复杂性：求解问题的某一个算法的复杂性计算复杂性：能求问题精确解的那个最快的算法的复杂性计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度问题的计算复杂性计算机在有限时间内能够求解的--【可求解问题】计算机在有限时间内难于求解的--【难求解问题】计算机完全不能求解的--【不可计算问题】由算法复杂性到计算复杂性计算复杂性还是没有回答怎样才是有限时间？继续…

当算法的复杂度是一个多项式，如O(n2)时，则对于大规模问题，该算法是可以在有限时间内被计算机完成的。例如，某一问题的贪心算法

O(n3)

。当算法的复杂度是用指数函数表示如O(2n)或阶乘函数表示如O(n!)，则当n很大（如10000）时，该算法是计算机在有限时间内无法处理的。例如某一问题的遍历算法O(n!)。O(1),O(logn),O(n),O(nlogn),O(nb)O(bn),O(n!)由算法复杂性到计算复杂性有限时间内是否能完成算法的执行？【P类问题】多项式问题(PolynomialProblem)，即：可以找出一个呈现O(na)复杂性算法求出精确解的问题，其中a为常数。P类问题是指计算机可以在有限时间内能求出精确解的问题，【NP类问题】非确定性多项式问题(Non-deterministicPolynomial)，即：可以找出一个呈现O(na)复杂性算法来验证一个可能解是否是正确的问题。

有些问题，其答案无法直接计算得到，但可通过间接的猜算/试算来得到，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解，但给定一个解却不难在多项式时间内验证其正确性的问题，即是NP类问题。【NPC类问题】完全非确定性多项式问题(NP-Complete)，即：(1)如果NP问题的所有可能解都可以在多项式时间内进行验算，(2)求精确解需要遍历所有可能解，(3)遍历所有可能解的复杂度是指数或阶乘级别的；则为NP-Complete问题。一个NP问题，并非其每个解都可以在多项式时间内验算，即：有些解是可以验算的，而有些解是不能验算的。如果一个NP问题其需要验算的解空间是用非多项式函数(指数函数或阶乘函数)来表达的，则是NP-Complete问题。如果一个NP问题经过约简后得到的问题仍旧是NP问题，则是NP-Complete问题。问：加密算法应该设计成一个什么问题呢？可求解与难求解问题用计算复杂性划分问题NP-Hard/NP难问题可求解与难求解问题可解性问题与难解性问题P类问题（多项式时间内能求精确解）NP类问题（多项式时间内能验证一个解）NPC类问题（1)多项式时间内能验证每一个解,(2)求精确解需要遍历解空间,(3)指数时间遍历解空间难解性问题非NP问题多项式时间内不一定能验证一个解穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解可能是O(n!)或O(an)近似解求解算法---近似解应该是O(na)∆=|近似解–精确解|满意解：∆充分小时的近似解进化算法，遗传算法，蚁群算法，蜂群算法,…NPC类问题NPC类问题求解