算法–切割的数组

算法–切割的数组

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。


标题来源:编程之美2.18

有一个无序的,元素个数为2n的正整数的数组,要求:

怎样能把这个数组切割为元素个数为n的两个数组,使得两个子数组的和尽量接近。

解析:由于两个子数组的和是一定的,等于整个数组的和。如今要求使得两个字数组的和尽量的接近,也就意味着要从当中选出n个数使得这n个数的和尽可能的接近sum/2,最好还是设为从小于sum/2的方向接近。于是。这就是一个01背包的问题:

如今有2N个物品,每一个物品的重量为A[i],有一个背包的大小为sum/2,如今从中挑选出N个物品,使得背包尽可能的被装满。

于是定义递推式为:

dp[i][j][v] = max(dp[i-1][j][v], dp[i-1][j-1][v-A[i]]+A[i]);

dp[i][j][v] :从前i个物品中选择j个,重量不大于v的最大的和。

上述print部分是在打印当中的一个子数组。返回的是终于的两个数组的最小的差值。

时间复杂度为: O(N*N*sum)

拓展:假设上述代码仅仅是要求计算终于的差值,而不须要打印出结果数组的话。那么我们就能够将时间复杂度减少到N*sum.

代码为:


终于的结果是f[N][v]==true的最大的v的值即为所求。(v是从sum/2開始依次减小)。


版权声明:本文博主原创文章。博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117122.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java 日志处理[通俗易懂]

    java各日志组件介绍common-logging(同时也称JCL)  common-logging是apache提供的一个通用的日志接口。用户可以自由选择第三方的日志组件作为具体实现,像log4j,或者jdk自带的logging,common-logging会通过动态查找的机制,在程序运行时自动找出真正使用的日志库。当然,common-loggi…

  • 关于numpy的astype(bool)和astype(int)等等[通俗易懂]

    关于numpy的astype(bool)和astype(int)等等[通俗易懂]关于numpy的astype(bool)和astype(int)等等importnumpyasnpa=[[1,2,1],[2,3,5]]b=[[0,0,0],[2,3,5]]c=np.array(a)d=np.array(b)print(c)print(d)就是简单的把list列表转化为数组然后看看加了.astype(bool)是什么意思?正如astype的中文意思,…

  • WDA Architecture

    WDA Architecture忙了一阵子,把我学习WD的计划打乱了,今天终于有点时间可以开学了,先转篇网文先.原文地址:http://moonroom1.spaces.live.com/blog/cns!7578AFCD9C32F7B1!443.ent…

  • 开发大数据基础教程(前端开发入门)

    第一阶段linux+搜索+hadoop体系第一阶段:linux+搜索+hadoop体系Linux大纲这章是基础课程,帮大家进入大数据领域打好Linux基础,以便更好地学习Hadoop,hbase,NoSQL,Spark,Storm,docker,kvm,openstack等众多课程。因为企业中无一例外的是使用Linux来搭建或部署项目。1)Linux的介绍,Linux的安装:VMwareW…

  • 静态代理理解_如何做代理

    静态代理理解_如何做代理静态代理现在如果要对每个..

    2022年10月16日
  • listView1.SelectedItems选中行要注意count>0[通俗易懂]

    listView1.SelectedItems选中行要注意count>0[通俗易懂]在右边的ListView中选中一行,就把选中行的第二列里的值显示在textBox里 。但是当我第一次选择一行时没有什么问题,当我第二次选择一行时就出现下面的错误:未处理ArgumentOutOfRangeException InvalidArgument=“0”的值对于“index”无效。  参数名:index上网查找说是要加一句判断if(listView1.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号