算法–切割的数组

算法–切割的数组

大家好,又见面了,我是全栈君,今天给大家准备了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)


相关推荐

  • Unrecognized Windows Sockets error: 0: JVM_Bind

    Unrecognized Windows Sockets error: 0: JVM_BindUnrecognized Windows Sockets error: 0: JVM_Bind

  • Django(74)drf-spectacular自动生成接口文档「建议收藏」

    Django(74)drf-spectacular自动生成接口文档「建议收藏」介绍drf-spectacular是为DjangoRESTFramework生成合理灵活的OpenAPI3.0模式。它可以自动帮我们提取接口中的信息,从而形成接口文档,而且内容十分详细,再也不

  • CTK Plugin Framework简介

    CTK Plugin Framework简介CTKPluginFramework简介 框架简介 1.1、简介CTKPluginFramework设计参考了OSGi(OpenServiceGatewayInitiative,开放服务网关协议)(Java的动态组件系统),并提供了一种能让应用程序(动态地)由许多不同的可重用组件组成的开发模型,允许通过服务进行通信。OSGi规范的核心部分是一个框架,核心框架定义了应用程序的生命周期模式和服务注册。基于OSGI核心框架定义了大量的OSGi服务:日志、配置管理、HTTP(运行se

  • 微信怎么设置自动回复机器人_微信群助手机器人

    微信怎么设置自动回复机器人_微信群助手机器人“傻瓜式”微信自动回复机器人配置教程首先下载Python和Pip到官网上去下源文件Python官网下载,Pip下载地址这里建议Pip不要直接在这下,后面会有提到。我下的是Python2.7.8,Python3可能和这个版本有点小区别。官网下的Python是安装文件,Pip则是免安装的源文件(我是将Python直接装在C盘,我把Pip中放在Python27目录里面)。…

  • vscode前端常用插件

    vscode前端常用插件vscode前端差用插件

  • MacBook —— 修改host文件「建议收藏」

    MacBook —— 修改host文件「建议收藏」文章目录MacBook——修改host文件MacBook——修改host文件打开Finder输入快捷键打开Finder输入快捷键Command+Shift+G,在弹出框中输入/etc/hosts:点击“前往”:打开hosts文件(用文本编辑即可)修改会出现没有权限的提示,我们点击“复制”然后修改完内容,将文件拷贝回这个地址,试图覆盖它,系统会出现下面的…

    2022年10月12日

发表回复

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

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