如何以最佳方式划分一个数组分成两个子阵列，因此在两个元素的总和相同。否则给出错误 [英] How to optimally divide an array into two subarrays so that sum of elements in both are same . otherwise give an error

问题描述

如何以最佳方式划分一个数组分成两个子阵列，因此在两个元素的总和相同。否则给出错误

实施例1：10，20，30，5，40，50，40，15

阵列可以被划分为10，20，30，第5，40和50，40，15。总和= 105每

实施例2：10，20，30，5，40，50，40，10

磁盘阵列不能被划分为2个数组等于总和

解决方案

 公共类问题1 {

公共静态无效的主要（字串[] args）抛出IOException异常{
    扫描仪扫描=新的扫描仪（System.in）;
    ArrayList的＆LT;整数GT;阵列=新的ArrayList＆LT;整数GT;（）;
    诠释案件;
    的System.out.println（请输入测试用例）;
    例= scanner.nextInt（）;

    的for（int i = 0; I＆LT;案件;我++）{
        INT大小;


        大小= scanner.nextInt（）;
        的System.out.println（输入初始数组的大小：）;

        对于（INT J = 0; J＆LT;大小; J ++）{
            的System.out.println（请输入数组中的元素）;
            INT元;
            元= scanner.nextInt（）;
            array.add（元）;
        }
    }

    如果（验证（阵列））{
的System.out.println（阵列可以分成）;}
  其他{
     的System.out.println（错误）;}

}

公共静态布尔验证（ArrayList中＆LT;整数GT;数组）{
    布尔标志= FALSE;
    Collections.sort（阵列）;
    的System.out.println（阵列）;
    INT指数= array.size（）;

    ArrayList的＆LT;整数GT; SUB1 =新的ArrayList＆LT;整数GT;（）;
    ArrayList的＆LT;整数GT; SUB2 =新的ArrayList＆LT;整数GT;（）;

    sub1.add（array.get（指数-1））;
    array.remove（指数-1）;

    指数= array.size（）;
    sub2.add（array.get（指数-1））;
    array.remove（指数-1）;

    而（！array.isEmpty（））{

    如果（compareSum（SUB1，SUB2））{
        指数= array.size（）;
        sub2.add（array.get（指数-1））;
        array.remove（指数-1）;
    }
    其他{
        指数= array.size（）;
        sub1.add（array.get（指数-1））;
        array.remove（指数-1）;
    }
    }

    如果（sumOfArray（SUB1）.equals（sumOfArray（SUB2）））
        标志=真正的;
    其他
        标志= FALSE;

    返回标志;
}

公共静态整数sumOfArray（ArrayList中＆LT;整数GT;数组）{
    迭代器＆LT;整数GT;它= array.iterator（）;
    整数总和= 0;
    而（it.hasNext（））{
        总和+ = it.next（）;
    }

    返回总和;
}

公共静态布尔compareSum（ArrayList中＆LT;整数GT; SUB1，ArrayList的＆LT;整数GT; SUB2）{
    布尔标志= FALSE;

    INT SUM1 = sumOfArray（SUB1）;
    INT SUM2 = sumOfArray（SUB2）;

    如果（SUM1＆GT; SUM2）
        标志=真正的;
    其他
        标志= FALSE;

    返回标志;
}

}
 

//贪婪的方法//

How to optimally divide an array into two subarrays so that sum of elements in both are same . otherwise give an error

Example 1: 10, 20 , 30 , 5 , 40 , 50 , 40 , 15

array can be divided as 10, 20, 30, 5, 40 and 50, 40, 15 . sum = 105 each

Example 2: 10, 20, 30, 5, 40, 50, 40, 10

array can not be divided into 2 arrays of equal sum

解决方案

public class Problem1 {

public static void main(String[] args) throws IOException{
    Scanner scanner=new Scanner(System.in);
    ArrayList<Integer> array=new ArrayList<Integer>();
    int cases;
    System.out.println("Enter the test cases");
    cases=scanner.nextInt();

    for(int i=0;i<cases;i++){
        int size;


        size=scanner.nextInt();
        System.out.println("Enter the Initial array size : ");

        for(int j=0;j<size;j++){
            System.out.println("Enter elements in the array");
            int element;
            element=scanner.nextInt();
            array.add(element);
        }
    }

    if(validate(array)){
System.out.println("Array can be Partitioned");}
  else{
     System.out.println("Error");}

}

public static boolean validate(ArrayList<Integer> array){
    boolean flag=false;
    Collections.sort(array);
    System.out.println(array);
    int index=array.size();

    ArrayList<Integer> sub1=new ArrayList<Integer>();
    ArrayList<Integer> sub2=new ArrayList<Integer>();

    sub1.add(array.get(index-1));
    array.remove(index-1);

    index=array.size();
    sub2.add(array.get(index-1));
    array.remove(index-1);

    while(!array.isEmpty()){

    if(compareSum(sub1,sub2)){
        index=array.size();
        sub2.add(array.get(index-1));
        array.remove(index-1);
    }
    else{
        index=array.size();
        sub1.add(array.get(index-1));
        array.remove(index-1);
    }   
    }

    if(sumOfArray(sub1).equals(sumOfArray(sub2)))
        flag=true;
    else
        flag=false;

    return flag;
}

public static Integer sumOfArray(ArrayList<Integer> array){
    Iterator<Integer> it=array.iterator();
    Integer sum=0;
    while(it.hasNext()){
        sum +=it.next();
    }

    return sum;
}

public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){
    boolean flag=false;

    int sum1=sumOfArray(sub1);
    int sum2=sumOfArray(sub2);

    if(sum1>sum2)
        flag=true;
    else
        flag=false;

    return flag;
}

}

// The Greedy approach //

这篇关于如何以最佳方式划分一个数组分成两个子阵列，因此在两个元素的总和相同。否则给出错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！