题目:有一个无序、元素个数为2n的正整数数组,要求:如何能把这个数组分割为元素个数为n的两个数组,并使两个子数组之和最接近?
看了编程之美的算法,一直在想算法只求出了最接近的那个和值,没有求出分割的具体分法,后来想想,这个具体的分割的索引值,可以在求和值的时候一起保存下来。代码有点乱,凑活看吧。
import java.util.*;
class Node{
int value;
List index = new ArrayList();
}
public class Main{
public static void main(String[] args){
int a[] = {1,5,7,8,9,6,3,11,20,17};
//题意保证了a.length一定为偶数
int n = a.length/2;
int sum = 0;
//Heap[i]表示存储从a中取i个数所能产生的和之集合的集合
List[] Heap = new List[n+1];
for(int i=0;i<n+1;i++){
Heap[i] = new ArrayList();
}
//计算数组总和
for(int i=0;i<2*n;i++){
sum += a[i];
}
//初始化Heap[0]
Node node = new Node();
node.value = 0;
Heap[0].add(node);
for(int k=1;k<=2*n;k++){
int updateIndex = min(n-1,k-1);
for(int j=updateIndex;j>=0;j--){
for(int i=0;i<Heap[j].size();i++){
Node oldNode = (Node)Heap[j].get(i);
int num = oldNode.value;
List list = oldNode.index;
//只加入小于等于sum/2的那些值
if(num+a[k-1]<=sum/2){
Node newNode = new Node();
newNode.value = num+a[k-1];
Iterator iterator = list.iterator();
while(iterator.hasNext()){
newNode.index.add(iterator.next());
}
newNode.index.add(k-1);
Heap[j+1].add(newNode);
}
}
}
}
//实现比较
Comparator orderValue = new Comparator(){
public int compare(Object o1, Object o2){
Node n1 = (Node)o1;
Node n2 = (Node)o2;
return n1.value-n2.value;
}
};
Collections.sort(Heap[n],orderValue);
Node h_node = (Node)Heap[n].get(Heap[n].size()-1);
System.out.println(h_node.value);
List h_list = h_node.index;
for(int i=0;i<h_list.size();i++){
System.out.print(h_list.get(i)+" ");
}
System.out.println();
}
private static int min(int x, int y){
return x<y?x:y;
}
}
分享到:
相关推荐
数组分割问题(印象深刻)1
最长上升子序列 编辑距离问题、货物堆积问题、骑士周游问题、数组分割问题、资源分配问题、最长上升子序列问题
是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. ...
arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。 我们最多能将数组分成多少块?
内容涵盖了Halcon的基础算子、高阶算子、数组操作、分割算法、字符检测、模板匹配、特征点检测与描述、3D重建、图像配准、图像融合、视频处理、机器学习与深度学习、实时图像处理、交互式图像处理、图像质量评价、...
split() 方法用于把一个字符串分割成字符串数组。这篇文章给大家介绍js中split()方法得到的数组长度问题,感兴趣的朋友一起看看吧
最近在C++编程中经常遇到需要多字节字符与宽字节字符相互转换的问题,自己写了一个类来封装wchar_t与char类型间的转换
同时利用分割的思想为以y坐标排序的数组中,不需要每次都排序,而只需要使用它的父问题传入的y排序数组切割掉一部分即可,而最初的排序源于一次快排。算法一共递归logn次,每层计算量都为n,而主函数调用两次快排,...
1. **0/1背包问题**:这是背包问题最基本的形式,要求对于每个物品,只能选择装入背包或者不装,不能分割物品。 2. **动态规划解法**:背包问题通常使用动态规划来求解。动态规划的思路是构建一个二维数组dp[i][j],...
leetcode数组下标大于间距 problems 1.Exercise LongnumAdd:字符串大整数相加 divideapple:数学规律,...bestsubstring:将字符串尽可能分割为多个部分,各子串不包含相同字符暴力 2pow:计算2的N次幂 dp/ chrous:相
一、迭代法 ... 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。
估计有的易友可能想到了"分割文本, 发送文本数组"。首先"发送文本数组", 我不喜欢, 有时候显得麻烦.其次"分割文本", 你可能会遇到这样以下这样的情况, 也就是sql字符串中出现了";", 你能怎么办? 你也很绝望对吧?...
可以运行的查找第K小元素的实现代码。并且实现了多个元素相同的算法。与王晓东的《算法》配套
这是因为数组被递归地分成两半,直到它不能再被分割,即到达单个元素。 当数组被“重建”或元素merge() ,它们也会被递归地比较和组合。 空间复杂度通常是未排序的二维数组中元素的数量。 但是我的实现使用临时数组...
书中列出了C用户经常问的400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预处理器等各个方面的主题,并分别给出了解答,而且结合代码示例阐明要点。 《你必须知道的495个C语言问题》结构...
1.23 能否声明和传入数组大小一致的局部数组,或者由其他参数指定大小的参数数组? 1.24 我在一个文件中定义了一个extern数组,然后在另一个文件中使用,为什么sizeof取不到数组的大小? 声明问题 1.25 函数只...
修复thead复制没有底部分割线的问题 修复thead复制时无背景色的问题 增加复选框同步功能(如果是JS代码设置复选框选中,需要调用 .setCheckBoxSync()方法) .setCheckBoxSync 方法参数说明:4种参数 1) 复...