课程介绍

学习资料

来源：广州童程童美信息学奥赛学校时间：2023/9/23 15:02:29

广州青少年学信息学奥赛排名机构

广州青少年学信息学奥赛排名机构，信息学编程培训推荐排名好的广州童程童美信奥赛编程培训机构。开设的乐高大颗粒、Scratch编程、Python编程、青少年信息学奥赛、JavaScript网页编程、手机APP编程、乐高WeDo、乐高EV3等全部课程巧妙融合。学习路线+竞赛路线，学习成长、比赛得奖双丰收。线下课程+线上课程，校区学习、在家学习皆可选。遍布50多座城市，开设230多家中心，14万名学员同时选择学习的科技素质教育公司，学的人多自然是好。
　　童程童美信息学奥赛编程培训班，主要面向及以上的中学生，课程内容主要使用C++语言培训。学员可参加等级测评，如果您也想学习信息学奥赛编程就快来加入我们吧。
　　动态规划法(Dynamic planning)介绍：动态规划的解法类似于分治法，都是先将一个大的问题分解成一个小的问题，再进行求解。然后有些问题使用分治法，会遇到很多相同的子问题，因此在求解过程中会出现过多的重复性计算。动态规划法主要采用表格的形式，动态地将每一个阶段每一状态的zui优解记录下来，确保之后迭代过程利用到的都是zui优解。
　　为了降低时间复杂度，我们就需要利用以空间换时间的思想，利用动态规划法，将已经计算过的子问题存到一定的空间内，等再次需要用到的时候取出来。
　　问题：假设有物品若干个，物品的重量分别为6、5、3、2，价值分别为15、10、8、4，背包zui大的承重量是10，怎样选择使得背包里容纳的物品价值zui高？
　　解题思路：每个物品都有两种状态：放与不放，即为0或1，如果使用蛮力法进行求解，时间复杂度为O(2^n)，显然当n越大时，它的
　　数量级大的难以想象，现在采用动态规划来降低这个复杂度并求解问题。
　　设物品集A，含有n个物品，它的重量为A.w={6,5,3,2}，它的价值为A.v={15,10,8,4}，承重为total=10，则P(A，total)为zui优解。
　　若当前允许的承重量j<w(某一物品重量)，选择不放入该物品，此时的P内允许的承重不变，并且该物品就从物品集中摘出。
　　P(A,total)=P(A_{n-1},total)
　　若当前允许的承重量j>=w(某一物品重量)，选择放入该物品，包里的价值增加了v(当前物品的价值)，此时的P内允许的承重就降低，并且该物品就从物品集中摘出。
　　P(A,total)=P(A_{n-1},total-w)+v
　　因此我们zui优解的递推公式为：
　　P(A,total)=left{begin{matrix}0,&j=0||i=0\P(A_{n-1},total),&j<A.w\P(A_{n-1},total-w)+v,&j>=A.wend{matrix}right.
　　根据递推公式我们可以进行动态规划的填表了。
　　重量价值
　　物品序号/
　　承重
　　0 1 2 3 4 5 6 7 8 9 10
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0
　　6 15 1 0 0 0 0 0 0 15 15 15 15 15
　　5 10 2 0 0 0 0 0 10 15 15 15 15 15
　　3 8 3 0 0 0 8 8 10 15 15 18 23 23
　　2 4 4 0 0 4 8 8 12 15 15 19 23 23
　　接下来具体的代码是用Python来实现的，完整代码如下。
　　#coding:utf-8
　　def max_value(w,v,total):n=len(v)pre=[([0]*(total+1))for i in range(n+1)]for i in range(1,n+1):for j in range(1,total+1):if j>=w[i-1]:key=max(pre[i-1][j],pre[i-1][j-w[i-1]]+v[i-1])#项为同样重量阶段下个状态的权值，第二项为重量除去该状态的重量加上现有权值pre[j]=keyelse:pre[j]=pre[i-1][j]print(pre[j])for i in range(n+1):print(pre)
　　if __name__=="__main__":total=10#w=[2,3,5,7]#v=[3,4,7,9]w=[6,5,3,2]v=[15,10,8,4]max_value(w,v,total)
　　想了解更多可以和页面右面的客服取得联系，也可拨打页面上方的电话，我们期待您的咨询！

信息学编程奥林匹克竞赛