CODEWITHSUNDEEP
javaarraysalgorithm
user3198603
user3198603

Reputation: 5816

Divide array into two subarray so that difference between array's sum is minimum?

Input is[4,13,14,15,16]. Output should be [16,15] and [14,13,4].

I can think of the following algorithm where

  1. I sort the array in descending order
  2. Take first two elements in two list
  3. Now add the element in list who sum is minimum
public class TestMinDiff {

    public static void main(String[] args) {
        Integer[] array = {4,13,14,15,16};

        Arrays.sort(array, Collections.reverseOrder());

        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();

        int list1Sum = 0;
        int list2Sum = 0;

        for(int i: array) {
            if(list1Sum<=list2Sum) {
                list1Sum = list1Sum + i;
                list1.add(i);
            } else {
                list2Sum = list2Sum + i;
                list2.add(i);
            }
        }
    }
}

Output is

  1. List 1 is [16,13,4].
  2. List 2 is [15,14].

Looks like my algorithm needs to be improved further. To me it looks like it is an NP problem. But I am not able to think of an algorithm here which gives me the output [16,15] and [14,13,4].

Upvotes: 2

Views: 2071

Answers (3)

M Sach
M Sach

Reputation: 34424

I agree with Nayuki algorithm. Its knapsack problem with one dimension where you can consider value for all inputs same as inputs(or weights).

Now find two sub arrays whose is sum is less than equal to 31

import java.util.ArrayList;
import java.util.List;
public class Knapsack {

    public static void main(String[] args) {

        int[] weight = {4,13,14,15};
        int[] value = {4,13,14,15};
        int targetSum = 31;

        knapsack(weight, value, targetSum);

    }

    public static void knapsack(int[] weight, int[] value, int targetSum) {

        int[][] weightValMatrix = new int[weight.length + 1][targetSum + 1];

        for (int i = 0; i < weight.length; i++) {
            for (int k = 0; k < targetSum + 1; k++) {
                weightValMatrix[i][k] = 0;
            }

        }

        for (int i = 1; i < weight.length + 1; i++) {
            for (int k = 1; k < targetSum + 1; k++) {
                if (k < weight[i - 1]) {
                    weightValMatrix[i][k] = weightValMatrix[i - 1][k];
                } else {
                    int valueInclusiveCurrentWeight = value[i - 1];
                    if ((k - weight[i - 1]) > 0) {
                        valueInclusiveCurrentWeight = valueInclusiveCurrentWeight
                                + weightValMatrix[i - 1][k - weight[i - 1]];
                    }

                    int valueExcludingCurrentWeight = weightValMatrix[i - 1][k];
                    weightValMatrix[i][k] = valueInclusiveCurrentWeight >= valueExcludingCurrentWeight ? valueInclusiveCurrentWeight
                            : valueExcludingCurrentWeight;

                }

            }



        }



        for (int i = 1; i < weight.length + 1; i++) {

            for (int k = 1; k < targetSum + 1; k++) {

                System.out.print(weightValMatrix[i][k]);

                if(k == targetSum){
                    System.out.println("");
                }
            }
        }


        System.out.println("final value is " + weightValMatrix[weight.length][targetSum]);

        List<Integer> finallySelectedWeightIndex = new ArrayList<Integer>();

        findActualWeightIndex(weightValMatrix, weight.length, targetSum, finallySelectedWeightIndex, weight);

        for(int index:finallySelectedWeightIndex){
            System.out.println("weight is " + weight[index-1] + " value is "+ value[index-1]);
        }


    }


    public static void findActualWeightIndex(int[][] weightValMatrix, int row, int column, 
            List<Integer> finallySelectedWeightIndex, int[] weight) {

        if(row==0 || column==0){
            return;
        }

        if(weightValMatrix[row][column]==weightValMatrix[row-1][column]){
            findActualWeightIndex(weightValMatrix, row-1, column, finallySelectedWeightIndex, weight);
        }else{
            finallySelectedWeightIndex.add(row);
            findActualWeightIndex(weightValMatrix, row-1, column - weight[row-1] , finallySelectedWeightIndex, weight);
        }
    }

}

Upvotes: 1

Masoud AMR
Masoud AMR

Reputation: 134

I understand your question this: you want divide array to two array that sum of each array minimum. you should compare list1Sum and list2Sum after add i, so:

if(list1Sum + i <= list2Sum){
            list1Sum= list1Sum +i;
            list1.add(i);
        }else{
            list2Sum= list2Sum +i;
            list2.add(i);
        }

Upvotes: 1

Nayuki
Nayuki

Reputation: 18533

This is the knapsack problem. It is NP-complete in the general case, but for small integers it can be solved effectively.

Let's take your example array of [4,13,14,15,16]. The total is 62. We rephrase this into a knapsack problem where we have this set of items, but the knapsack capacity is 62÷2 = 31. If we select items that total to the largest number no greater than 31, then this solves your problem of minimizing the difference between the two divided lists.

There is a standard algorithm for solving the knapsack problem, which I won't explain here.

Upvotes: 6

Related Questions