首页 > 代码库 > 算法之--数组分割
算法之--数组分割
题目来源:编程之美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的最大的和。
<script src="https://code.csdn.net/snippets/444832.js" type="text/javascript"></script>
上述print部分是在打印其中的一个子数组,返回的是最终的两个数组的最小的差值。
时间复杂度为: O(N*N*sum)
拓展:如果上述代码只是要求计算最终的差值,而不需要打印出结果数组的话,那么我们就可以将时间复杂度降低到N*sum.
代码为:
<script src="https://code.csdn.net/snippets/444836.js" type="text/javascript"></script>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。