首页 > 代码库 > 将数组分为两部分,使得这两部分和最接近,返回这两部分的差值
将数组分为两部分,使得这两部分和最接近,返回这两部分的差值
【问题】将数组分为两部分,使得两部分的和最接近,返回两部分的差值。例如:
int[] array={1,0,1,7,2,4},分为两部分为{1,0,1,2,4},{7},差值为1。
参考1:《编程之美》第2.18节,不过问题有所不同,2.18节要求长度为2n的数组分为两个长度为n的数组,使得两部分和最接近。
参考2:http://www.tuicool.com/articles/ZF73Af
【思路】动态规划的解法。求得array的和sum,问题转化为:在array中选取若干个元素,使得这些元素的和<=sum/2,且是最接近sum/2的元素集合。
开一个数组:int[][]f=new int[length+1][sum/2+1]
状态方程:f[i][j]=Max(f[i-1][j-array[i]]+array[i],f[i-1][j])
解释:f[i][j]表示array中i个元素的和<=j,且是最接近j的元素集合。f[i-1][j-array[i]]表示array中i-1个元素的和最接近j-array[i],所以f[i][j]应该是[i-1][j-array[i]]+array[i]和f[i-1][j]中最大的那个。有点像0-1背包问题。
** * 创建时间:2014年10月7日 下午8:52:57 项目名称:Test * * @author Cao Yanfeng * @since JDK 1.6.0_21 类说明:将数组分为两部分,使得这两部分和最接近,返回这两部分的差值 注意:不要求将数组平均分 */ public class DivideArrayTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] array = { 1, 0, 1, 7, 2, 4 }; System.out.println(getMaxDiff(array)); } /* f[i][j]表示i个元素装容量为j的背包能装的最大容量 */ public static int getMaxDiff(int[] array) { int sum = getSum(array); int length = array.length; int[][] f = new int[length + 1][sum / 2 + 1]; for (int i = 0; i < length; i++) { for (int j = 1; j <= sum / 2; j++) { f[i + 1][j] = f[i][j]; if (array[i] <= j && f[i][j - array[i]] + array[i] > f[i][j]) { f[i + 1][j] = f[i][j - array[i]] + array[i]; } } } return sum - 2 * f[length][sum / 2]; } public static int getSum(int[] array) { int sum = 0; for (int i = 0; i < array.length; i++) { sum += array[i]; } return sum; } }
将数组分为两部分,使得这两部分和最接近,返回这两部分的差值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。