大家好，又见面了，我是全栈君，今天给大家准备了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開始依次减小）。
版权声明：本文博主原创文章。博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117122.html原文链接：https://javaforall.net
