Java算法系列背包问题衾影の学习树洞

背包问题是动态规划算法中非常经典的一类问题,也是笔试面试中常见的一类问题。

背包问题有四类:0/1背包问题、完全背包问题、多重背包问题、混合背包问题。

下面将总结0/1背包问题、完全背包问题、多重背包问题三类问题。对于混合背包问题,难度较大,一般笔试面试题也不会过多涉及。

笔者自认为本文将背包问题总结地比较全面,可难免有错漏,欢迎批评指正!

你有一个背包,最多能容纳的重量是m。现在有n个物品,第i个物品的重量为w[i],价值为v[i]。求这个背包至多能装多大价值的物品?

动态规划是一个将大问题划分为小问题进行解决,从而一步步获取最优解的过程。对于0/1背包问题,考虑子问题“求解将前i个物品放入容量为j的背包中的最大价值”,设F(i,j)为将前i个物品放入容量为j的背包中最优解的总价值。对于第i个物品,事实上有两种情况:

(注意理解上述过程:是先比较第i个物品的重量与背包容量,若能放,再比较放入第i个物品与不放入第i个物品哪个能得到前i个物品情况下的最优解!)

因此可以得到递推公式:

$$初始条件:F(i,0)=F(0,j)=0\\$$

$$F(i,j)=\begin{cases}F(i-1,j),&w[i]>j\\max\{F(i-1,j),v[i]+F(i-1)(j-w[i])\},&w[i]≤j\end{cases}$$

给出如下一个例子:

背包的承重m=5。现在有4个物品如下,求背包至多能装多大价值的物品:

对于n=4,m=5的背包问题,应建立一个dp[n+1][m+1]的二维表。填表过程如下:

你是否对这个填表过程感到熟悉?是的,所谓背包问题,其实还是前面的二维动态规划问题!

填表过程的代码如下:

是的,本问题的核心思想就是“求解将前i个物品放入容量为j的背包中的最大价值”,而不同的物品顺序显然填出来的表是不相同的。但是,这个动态规划表并不是我们需要的结果,我们也并不关心”前i个物品放入容量为j的背包“的问题,我们关心的是“n个物品放入容量为m的背包”的问题。虽然不同物品顺序得出的动态规划表不一样,但其最优解的值一定是一样的,而这才是我们关心的。

接下来将介绍如何回溯得到最优方案。

我们先用图示的方法看看如何从动态规划表进行回溯、得出最优解的方案:

上述回溯过程似乎很复杂,但是在代码中可以加入一个辅助数组path[][]来记录更新的物品。则求出最优方案的代码如下:

publicstaticvoidknapsack2(int[]w,int[]v,intn,intm){int[][]dp=newint[n+1][m+1];int[][]path=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];else{if(dp[i-1][j]=0;i--){if(path[i][j]==1){System.out.println("放入第"+i+"个物品");j=j-w[i-1];//回溯过程体现在这里!}}System.out.println("最大价值为:"+dp[n][m]);}上文提到,不同的物品顺序得到的动态规划表不同,但最优解的值是相同的。但是,相同的只有最优解的值,由于最优解的方案是需要根据动态规划过程回溯得到的,因此最优解的方案却不一定一样。

例如将上例中物品1的价值修改为10,求得的最优解虽然同样是35,却存在{物品1,物品2,物品4}和{物品3,物品4}两个最优方案。你可以使用下面两个例子进行测试:

//示例1int[]w={2,1,3,2};//物品的重量int[]v={10,10,20,15};//物品的价值intn=w.length;//物品的个数intm=5;//背包的容量knapsack2(w,v,n,m);//示例2int[]w={3,1,2,2};//物品的重量int[]v={20,10,10,15};//物品的价值intn=w.length;//物品的个数intm=5;//背包的容量knapsack2(w,v,n,m);以上两个例子仅仅交换了物品的顺序,虽然最优解的值相同,但最优方案却不同。

那么,怎么判断最优解的方案是否唯一呢?在填表过程中,如果F[i-1][j]与v[i]+F[i-1][j-w[i]]相等,则可说明存在多个最优方案。

注:此方法不需掌握,可直接跳过。但是看完之后,相信你会对动态规划有更深一步的了解。

动态规划算法是自底向上的:动态规划算法从最小的子问题出发,使用较小子问题的解去填充表格,每个子问题只解一次。但是,有些较小的子问题的解常常不是必需的。

递归的算法是自顶向下的:递归算法对递推式的求解将导致需要不止一次地解公共的子问题。例如斐波那契数列问题,递归算法将多次重复计算相同值,因此效率非常低。

将自底向上的动态规划算法与自顶向下的递归算法结合起来,使它只对必要的子问题求解且只求解一次,这就是记忆功能的方法。该方法自顶向下地使用递归进行求解,但还需维护一个自底向上的动态规划表格:

publicclassMFKnapsackDemo{publicstaticvoidmain(String[]args){int[]w={2,1,3,2};//物品的重量int[]v={12,10,20,15};//物品的价值intn=w.length;//物品的数量intm=5;//背包的容量MFKnapsackmfKnapsack=newMFKnapsack(m,w,v);System.out.println("最大价值为:"+mfKnapsack.knapsack(n,m));}}classMFKnapsack{staticintn;//物品的个数staticintm;//背包的容量staticint[]w;//物品的重量staticint[]v;//物品的价值staticint[][]dp;//动态规划表/***将w[]、v[]、dp[][]作为全局变量*对于dp[][],将第0行、第0列初始化为0,其余全部初始化为-1*/publicMFKnapsack(intm,int[]w,int[]v){this.m=m;this.w=w;this.v=v;this.n=w.length;dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){dp[i][j]=-1;}}}publicstaticintknapsack(inti,intj){if(dp[i][j]<0){if(j

对比普通动态规划算法计算出的表格来看,加入记忆功能后,算法将只对必要的子问题进行求解。

回到经典的01背包问题,我们再看一看核心表达式:

$$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],v[i]+dp[i-1][j-w[i]]\},&w[i]≤j\end{cases}$$

可以看到,求解dp[i][j]时,其实只需要第i-1行的第j列或者第j-w[i]列的结果,其他行的结果是不需要的。所以我们真正需要的只有i-1这一行,在对i遍历时,第i层可以自动滚动覆盖掉第i-1层。

那么我们就可以进行空间优化,将其优化为一维数组:

$$dp[j]=\begin{cases}dp[j],&w[i]>j\\max\{dp[j],v[i]+dp[j-w[i]]\},&w[i]≤j\end{cases}$$

如果按照这个公式填表,会发现存在以下问题:

出现这个问题的原因是:从左向右遍历会导致,后修改的右边的值需要用到先修改的左边的值。

那么如何解决呢?很简单,将其修改为从右向左遍历即可:

根据填表过程,可以得到01背包问题的空间优化算法:

publicstaticintknapsack3(int[]w,int[]v,intn,intm){int[]dp=newint[m+1];for(inti=1;i<=n;i++){for(intj=m;j>=1;j--){//if(w[i-1]>j)dp[j]=dp[j];if(w[i-1]<=j)dp[j]=Math.max(dp[j],v[i-1]+dp[j-w[i-1]]);}}returndp[m];}1.5恰好装满问题你有一个背包,最多能容纳的重量是m。现在有n个物品,第i个物品的重量为w[i],价值为v[i]。若背包恰好装满,求至多能装多大价值的物品?如果无解请返回0。

若使用空间优化,则应初始化dp[0]为0,其余初始化为Integer.MIN_VALUE。

最后若dp[m]为正数则说明恰好装满,若为负数则说明无解。

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]v=newint[n];int[]w=newint[n];for(inti=0;i=1;j--){if(w[i-1]<=j)dp[j]=Math.max(dp[j],v[i-1]+dp[j-w[i-1]]);}}System.out.println(dp[m]);Arrays.fill(dp,Integer.MIN_VALUE);dp[0]=0;for(inti=1;i<=n;i++){for(intj=m;j>=1;j--){if(w[i-1]<=j)dp[j]=Math.max(dp[j],v[i-1]+dp[j-w[i-1]]);}}if(dp[m]<0)dp[m]=0;System.out.print(dp[m]);}}二、完全背包问题看到这里先问一下大家,为什么叫做0/1背包问题呢?因为在0/1背包问题中,对于所有的物品只有放与不放两种情况。而完全背包问题就不一样了,在完全背包问题中,每种物品都有无限件可用:

你有一个背包,最多能容纳的重量是m。现在有n种物品,每种物品有任意多个,第i个物品的重量为w[i],价值为v[i]。求这个背包至多能装多大价值的物品?

我们先看一看经典01背包问题的方程:

对于完全背包问题,由于每种物品有任意多个,那么我们可以再加入一层循环k,k代表第i种物品有k件。

则v[i]应修改为k*v[i],w[i]应修改为k*w[i],且应对遍历的k*v[i]+dp[i-1][j-k*w[i]]取最大值,因此可以得到完全背包问题的方程:

$$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],max\{k*v[i]+dp[i-1][j-k*w[i]]\}\},&w[i]≤k*w[i]≤j\end{cases}$$

代码如下:

观察完全背包问题的方程:

$$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j&①\\max\{dp[i-1][j],max\{k*v[i]+dp[i-1][j-k*w[i]]\}\},&w[i]≤k*w[i]≤j&②\end{cases}$$

我们发现,当k=0时,有dp[i-1][j]与k*v[i]+dp[i-1][j-k*w[i]]相等,故以上方程可以合并为:

$$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j&①\\max\{k*v[i]+dp[i-1][j-k*w[i]]\},&0≤k≤\frac{j}{w[i]}&②\end{cases}$$

对于式子②,我们知道有以下两种情况,二者的最大值即为dp[i][j]:

$$\begin{aligned}dp[i][j]&=max\{(k+1)*v[i]+f[i-1][j-(k+1)*w[i]]\}\\&=max\{k*v[i]+f[i-1][j-(k+1)*w[i]]\}+v[i]\\&=max\{k*v[i]+f[i-1][j-w[i]-k*w[i]]\}+v[i]\end{aligned}\\(0≤k≤j/w[i])$$

$$dp[i][j-w[i]]=max\{k*v[i]+dp[i-1][j-w[i]-k*w[i]]\}\\(0≤k≤j/w[i])$$

综合不放入的情况与放入的情况,两者应取最大值,因此式子②可以写为:

$$dp[i][j]=max\{dp[i-1][j],dp[i][j-w[i]]+v[i]\}\tag{w[i]≤j}$$

综上,结合式子①与式子②,因此完全背包问题的方程为:

$$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],dp[i][j-w[i]]+v[i]\},&w[i]≤j\end{cases}$$

因此可以写出代码:

publicstaticintCompleteKnapsack2(int[]w,int[]v,intn,intm){int[][]dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];elsedp[i][j]=Math.max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);}}returndp[n][m];}2.3改进2:空间优化观察完全背包问题的方程:

可以看到,求解dp[i][j]时,其实只需要第i-1行的第j列或者当前第i行已经求过的第j-w[i]列的结果,其他行的结果是不需要的。

$$dp[j]=\begin{cases}dp[j],&w[i]>j\\max\{dp[j],dp[j-w[i]]+v[i]\},&w[i]≤j\end{cases}$$

与0/1背包问题的空间优化不同,由于我们需要的第i行的第j-w[i]列在当前值j的左侧,因此我们必须对j从左向右遍历才能取到该值。

因此,空间优化后的完全背包问题的代码如下:

我们知道,动态规划是一个将大问题划分为小问题进行解决,从而一步步获取最优解的过程。

我们将F[i][j]表示为“将前i个物品放入容量为j的背包中的最大价值”,对于第i种物品,有两种情况:

怎么样?是不是更好理解了呢?

你有一个背包,最多能容纳的重量是m。现在有n种物品,每种物品有任意多个,第i个物品的重量为w[i],价值为v[i]。若背包恰好装满,求至多能装多大价值的物品?如果无解请返回0。

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]v=newint[n];int[]w=newint[n];for(inti=0;i=w[i-1])dp[j]=Math.max(dp[j],dp[j-w[i-1]]+v[i-1]);}}System.out.println(dp[m]);Arrays.fill(dp,Integer.MIN_VALUE);dp[0]=0;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(j>=w[i-1])dp[j]=Math.max(dp[j],dp[j-w[i-1]]+v[i-1]);}}if(dp[m]<0)dp[m]=0;System.out.print(dp[m]);}}三、多重背包问题你有一个背包,最多能容纳的重量是m。现在有n种物品,第i个物品的重量为w[i],价值为v[i],数量为c[i]。求这个背包至多能装多大价值的物品?

我们先观察完全背包问题的方程:

那么,多重背包与完全背包的区别在哪里呢?多重背包仅仅是对物品的数量多了个限制k≤c[i]:

$$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],max\{k*v[i]+dp[i-1][j-k*w[i]]\}\},&w[i]≤k*w[i]≤j&and&k≤c[i]\end{cases}$$

所以,仅仅需要对k循环的条件作修改即可。代码如下:

publicstaticintMultipleKnapsack1(int[]w,int[]v,int[]c,intn,intm){int[][]dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];else{inttemp=0;for(intk=1;k<=j/w[i-1]&&k<=c[i-1];k++){//对比完全背包,仅需修改此处temp=Math.max(temp,k*v[i-1]+dp[i-1][j-k*w[i-1]]);}dp[i][j]=Math.max(dp[i-1][j],temp);}}}returndp[n][m];}3.2改进1:空间优化同样的,多重背包问题可以进行空间优化,其思路与0/1背包问题一致,需要考虑到:若从左向右遍历,会导致后修改的右边的值需要用到先修改的左边的值。

因此,多重背包问题的j值需要从右向左遍历:

publicstaticintMultipleKnapsack2(int[]w,int[]v,int[]c,intn,intm){int[]dp2=newint[m+1];for(inti=1;i<=n;i++){for(intj=m;j>=1;j--){if(w[i-1]<=j){for(intk=1;k<=j/w[i-1]&&k<=c[i-1];k++){dp2[j]=Math.max(dp2[j],k*v[i-1]+dp2[j-k*w[i-1]]);}}}}returndp[m];}3.3改进2:二进制优化、单调队列优化多重背包问题还可以进行二进制优化、单调队列优化。但笔者才疏学浅,就不多作介绍了。

THE END
1.算法笔记(三)算法学习技巧总结 算法是一门数学科学院,想要学号算法即该算法是为了要解决什么问题,需要静下心来谢谢代码,与不写代码的人区别是效率比他妈呢提高了很多,算法学习还需要举一反三你,这样我们才能狗的更好。https://www.code456.com/article/3598351.html
2.算法总结最常用的五大算法(算法题思路)算法题技巧本文介绍了贪心算法的概念和实例,如Prim和Kruskal算法;分治法的思想及其在二分查找、快速排序和归并排序中的应用;动态规划的基本思想和Floyd算法、背包问题的示例;回溯法的原理以及在八皇后问题中的应用;分支限界法的基本思想和在单源最短路径问题中的应用。文章还探讨了这些算法之间的区别和联系。 https://blog.csdn.net/Jernnifer_mao/article/details/130220554
3.深度学习经典算法遗传算法详解遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体中的机会。个体适应度大的个体更容易被遗传到下一代。通常,求目标函数最大值的问题可以直图5-2正六边形筛选机制接把目标函数作为检测个体适应度大小的函数。 7、复制 程序设计流程https://developer.aliyun.com/article/1127575
4.经典算法问题来一个有这么一个算法题目,通过它我们来了解下码农是怎么学习算法:假设一堆人中有一个人可能是名人(明星),也有可能这人群中没有名人,名人满足的条件是人群中所有人都认识他,但是他不认识其他人,我们可以通过询问每个人来找出这个名人,那么假设我们只能问某个人是否认识另外一个这样的问题,得到回答也只能是认识或者不认识这https://m.acfun.cn/v/?ac=18548125&from=video&type=article_2
5.算法精粹:经典计算机科学问题的Python实现本书是一本面向中高级程序员的算法教程,借助Python语言,用经典的算法、编码技术和原理来求解计算机科学的一些经典问题。全书共9章,不仅介绍了递归、结果缓存和位操作等基本编程组件,还讲述了常见的搜索算法、常见的图算法、神经网络、遗传算法、k均值聚类算法、对抗搜索算法等,运用了类型提示等Python高级特性,并通过各级https://www.epubit.com/bookDetails?id=UB71fac289a9240
6.机器学习10大经典算法详解“数据+算法=模型”。面对具体的问题,选择切合问题的模型进行求解十分重要。有经验的数据科学家根据日常算法的积累,往往能在最短时间内选择更适合该问题的算法,因此构建的模型往往更准确高效。 本文归纳了机器学习的10大算法,并分别整理了各算法的优缺点及主要特征,供大家学习参考。读完本文,你将掌握以下机器学习10大算http://www.360doc.com/content/12/0121/07/27362060_1061639511.shtml
7.迁移学习(TransferLearning)的背景历史及学习2.机器学习框架与基本组成 3.机器学习的训练步骤 4.机器学习问题的分类 5.经典机器学习算法介绍 目标:机器学习是人工智能的重要技术之一,详细了解机器学习的原理、机制和方法,为学习深度学习与迁移学习打下坚实的基础。 二、深度学习简介与经典网络结构介绍 https://cloud.tencent.com/developer/article/2068121
8.多智能体路径规划综述本文首先对MAPF问题进行了阐述,概述了经典的集中式规划算法,详细分析了经典算法的原理,然后概述了深度强化学习,解析了主流的强化学习算法原理,将MAPF问题描述为强化学习问题,介绍了基于强化学习的MAPF算法研究进展。在此基础上,指出现有算法面临的挑战,指出了下一步要解决的问题和研究方向。 https://www.fx361.com/page/2022/1017/11262806.shtml
9.支持C++,Java,Python,Go,JavaScript等多语言版本,从此算法学习《代码随想录》LeetCode 刷题攻略:200道经典题目刷题顺序,共60w字的详细图解,视频难点剖析,50余张思维导图,支持C++,Java,Python,Go,JavaScript等多语言版本,从此算法学习不再迷茫! 来看看,你会发现相见恨晚! - GitHub - Coding4Real/leetcode-mashttps://github.com/Coding4Real/leetcode-master
10.五大经典算法之<递归算法及经典实例分析>学习目标: (一)了解递归算法思想? (二)用递归思想来理解和实现递归经典实例 I.阶乘问题? II.斐波那契问题? III.汉诺塔问题? IV.全排列问题 (一)递归 I. 定义? 递归算法(英语:recursion algorithm)在? ?计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。 需要满https://www.360doc.cn/mip/1127301487.html
11.路径规划中的DRL与OR算法:对比与展望因此,VRP在物流配送中有着广泛的应用场景,在过去50年来是研究热点。传统的优化方法(启发式、精确算法等)专注于研究各种各样的问题变形,甚至拓展到了uncertainty、robust、stochastic、two-echelon等场景,而深度强化学习类的方法则主要专注于求解TSP、CVRP等简单情形,并常用优化方法得到的解作为比较对象。下文将详细介绍。https://www.51cto.com/article/757803.html
12.字节跳动3数据结构与算法经典问题解析-Java语言描述目录 本文由曾供职于多家知名IT企业的资深软件架构师撰写,以Java为描述语言,介绍计算机编程中使用的数据结构和算法,覆盖相应竞争性考试的主题,目的不是提供关于数据结构和算法的定理及证明,而是强调问题及其分析,讲解必备知识和解题技巧。文中汇集知名IT企业经典的编程面试题目并给https://maimai.cn/article/detail?fid=1663985877&efid=TP99-4Gnjz5uI46gYIbONQ
13.AI工程师必备技能如果是凸函数,我们需要选择相应的优化方法论进行优化,因为优化问题是机器学习算法中的核心部分。 以上是对凸优化的方法论的一些总结与梳理,不得不说,凸优化是一个很深奥也很大的领域,并且通过一些非凸函数的优化方法论,也能感受出如果要严格解决一个数学问题,步骤是很严谨的,文中的观点如果有错误的地方,还请各路https://www.jiqizhixin.com/articles/2019-01-23-15
14.经典算法问题:数组中的逆序对这种思路虽然很直接,但编写出错的概率很低,在没有在线评测系统的时候,它可以作为一个“正确的”参考答案,用以检验我们自己编写的算法是否正确。 思路2:分治 这道题最经典的思路是使用分治法计算,借助“归并排序”的分治思想,排好序以后,逆序对就求出来了,时间复杂度为 https://www.jianshu.com/p/e6530cb7aa66
15.C/C++经典算法之约瑟夫问题详解C语言这篇文章主要给大家介绍了关于C/C++经典算法之约瑟夫问题的相关资料,约瑟夫环问题是一道经典的数据结构的题目,本文介绍了解决约瑟夫问题的三种方法,需要的朋友可以参考下https://www.jb51.net/article/218551.htm
16.常州科普网这样,发明者可以首先根据物场模型决定需要实现的基本功能,然后通过需要实现的功能很容易地找到与之对应的科学效应或科学现象,再根据这些科学效应或现象,产生解决问题的思路。 9、发明问题解决算法(ARIZ) ARIZ是俄文“发明问题解决算法”的缩写,英文缩写为AIPS,是发明问题解决过程中应遵循的理论方法与步骤。ARIZ是基于https://kx.jscz.org.cn/html/czkx/2022/LOMNAAD_0613/28486.html
17.贪心算法入门详解,经典实例分析在求解会议室效率问题时,我们虽然先基于动态规划思想做了分析,稍稍复杂了些,但最后还是能够结合贪心思想,设计出更加简洁的算法。 事实上,贪心策略是一种强有力的策略,可以很好的解决很多问题,在以后的学习中,我们可能会遇到许多基于贪心策略设计的算法,例如最小生成树算法,单元最短路径的 Dijkstra 算法等等。https://blog.popkx.com/2307/
18.科学网—[转载]进化集成学习算法综述在当前的研究方法中,一些研究分别对基于分类、回归和聚类问题的集成学习方法进行了综述。尽管这些研究对进化集成学习算法进行了简单的介绍,但并未对一些代表性的进化集成学习算法进行详细综述。并且在笔者目前查阅到的文献中,一些关于进化集成学习算法的综述只是针对分类、回归和聚类问题中的一种或两种,尚未发现有学者对包https://wap.sciencenet.cn/blog-951291-1312816.html
19.关于背包问题的一些理解和应用本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对《背包问题九讲》的理解)出发,帮助读者更快地学习《背包问题九讲》中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用。 2.背包问题及应用https://www.xiuzhanwang.com/a1/Cyuyan/3447.html
20.谷歌复用30年前经典算法,CV引入强化学习,网友:视觉RLHF要来了?该研究旨在学习以 θ 为参数的条件分布 P (y|x, θ),使奖励函数 R 最大化。用抽象的公式来形容,就是本文要解决以下优化问题。 问题有了,接下来就是怎么解决了,本文分两步走:首先用最大似然估计对模型进行预训练;然后使用 REINFORCE 算法对模型进行 Tuning 。下面我们看看这两步的具体过程:https://www.thepaper.cn/newsDetail_forward_22086240
21.每道题都会出现在试卷上(确信)新传热点真题答题总结No.04(下) 出题原因:就建立健全网络综合治理体系作出重要论述、提出明确要求,深刻阐释了“为什么要建、怎样建”等重大理论和实践问题,同时,网信办也大刀阔斧地开展“清朗”系列专项整治行动。从短视频与直播乱象,到算法与大数据技术带来的个人信息隐私安全问题,再到网络暴力、社交媒体舆论与舆情、平台反垄断等热点话题,都https://weibo.com/ttarticle/p/show?id=2309404933996114215589
22.DeepMind用神经网络求解MIP后,攻破运筹学只是时间问题?你想多了如果大量变量可以被固定,则可以把这个固定变量后的子问题当作一个全新的MIP求解,以期望可以找到高质量的整数解。由于大量的变量被固定了,子问题的搜索空间会变小,且预求解可以进一步的削减问题的规模,因此解子问题会相对容易些。 DeepMind提出的Neural Diving这个算法,是通过机器学习和神经网络,给定一个问题结构,预判https://yuanzhuo.bnu.edu.cn/article/805