Minimize the sum of product of two arrays with permutations allowed

http://www.geeksforgeeks.org/minimize-sum-product-two-arrays-permutations-allowed/

Given two arrays, A and B, of equal size n, the task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[n-1] * B[n-1]. Shuffling of elements of arrays A and B is allowed.

int minValue(int A[], int B[], int n)

{

    // Sort A and B so that minimum and maximum

    // value can easily be fetched.

    sort(A, A + n);

    sort(B, B + n);

    // Multiplying minimum value of A and maximum

    // value of B

    int result = 0;

    for (int i = 0; i < n; i++)

        result += (A[i] * B[n - i - 1]);

    return result;

}

http://www.geeksforgeeks.org/rearrange-array-minimize-sum-product-consecutive-pair-elements/

We are given an array of even size, we have to sort the array in such a way that the sum of product of alternate elements is minimum also we have to find that minimum sum.

For rearranging the array in such a way that we should get the sum of the product of consecutive element pairs is minimum we should have all even index element in decreasing and odd index element in increasing order with all n/2 maximum elements as even indexed and next n/2 elements as odd indexed or vice-versa.

Now, for that our idea is simple, we should sort the main array and further create two auxiliary arrays evenArr[] and oddArr[] respectively. We traverse input array and put n/2 maximum elements in evenArr[] and next n/2 elements in oddArr[]. Then we sort evenArr[] in descending and oddArr[] in ascending order. Finally, copy evenArr[] and oddArr[] element by element to get the required result and should calculate the minimum required sum.

int minSum(int arr[], int n)

{

    // create evenArr[] and oddArr[]

    vector<int> evenArr;

    vector<int> oddArr;

 

    // sort main array in ascending order

    sort(arr, arr+n );

 

    // Put elements in oddArr[] and evenArr[]

    // as per desired value.

    for (int i = 0; i < n; i++)

    {

        if (i < n/2)

            oddArr.push_back(arr[i]);

        else

            evenArr.push_back(arr[i]);

    }

 

    // sort evenArr[] in descending order

    sort(evenArr.begin(), evenArr.end(), greater<int>());

 

    // merge both sub-array and

    // calculate minimum sum of

    // product of alternate elements

    int i = 0, sum = 0;

    for (int j=0; j<evenArr.size(); j++)

    {

        arr[i++] = evenArr[j];

        arr[i++] = oddArr[j];

        sum += evenArr[j] * oddArr[j];

    }

 

    return sum;

}