Dynamic Programming - Flip minimum signs of array elements to get minimum sum of positive elements possible

Question

This is the question which is straightforwardly available on geeksforgeeks. Question Link

I am trying to understand the approach to solve this problem but have not been able to understand it yet. Can someone please explain the approach?

Thanks a lot!

Answer 1

***//we are just calculating all the possible sum and the the flips associated with it and returning the the one with smallest non negative sum possible***  
  
pair<int, int> f(int index, int sum, const vector<int> &arr){
    int n=arr.size();
    
    //base case
    if(index==n){
        if(sum<0)return {1e9, 1e9};
        else return {sum, 0};
    }
    
    //not flipped;
    auto op1=f(index+1, sum+arr[index], arr);
    
    // flipped
    auto op2=f(index+1, sum-arr[index], arr);
    op2.second++;
    
    return min(op1, op2);
    
    
    
}
int Solution::solve(const vector<int> &arr) {
    int n=arr.size();
    
    auto ans=f(0, 0, arr);
    return ans.second;
}

it is just the recurrence relation , you can optimise it further by memoization

Answer 2

This problem can be broken down to 0/1 knapsack problem. How?

The 0/1 knapsack problem has three inputs - A Values array, a Weights array, and a capacity C. The task is to pick/leave (pick entire items and one item can be picked only once) such that it maximizes the sum of values not exceeding the capacity C.

Consider the input array for the given flip array problem to be: [10, 14, 6].

The mappings to the knapsack problem are as follows: Values array and Weights array, both are same here: [10, 14, 6].

Lets discuss capacity C now: The given problem asks to find minimum number of flips in an array of positive integers that yield the minimum positive sum.

Calculate sum S, for all array elements = 30. Divide it by 2, S/2 = 15.

If we look at the question again, and try to map it to knapsack problem it can be observed that picking up the Numbers/Weights not exceeding capacity S/2(15) will yield the minimum possible positive sum.

For ex: [10, 14, 6]. Picking weights/numbers closest to 15 and flipping them will yield the minimum possible positive sum. Here pick 14, the other integers add up to 16. The difference is 2, the minimum possible positive sum in given case. It also becomes clear for every number chosen to be filled in our knapsack, it will contribute to the total flip count. In case of a tie, this information would be used to select the optimal option.

pair<int, int> compare(pair<int, int> a, pair<int, int> b) {
    if(a.first > b.first) return a;
    if(b.first > a.first) return b;
    int minFlips = min(a.second, b.second);
    return {a.first, minFlips};
}

pair<int, int> dfs(const vector<int> &A, int n, int capacity, vector<vector<pair<int, int>>> &dp) {
    // base cases

    // no items left, you can't pick anything and can't maximize anything
    // no capacity left, you can't pick anything and can't maximise anything

    // hence sum is zero
    // because nothing is picked, nothing is flipped, so flip count is also zero
    if(n == 0 || capacity == 0) {
        return {0, 0}; // sum, minFlips
    }

    // memoization condition
    if(dp[n][capacity].first != -1) {
        return dp[n][capacity];
    }

    pair<int, int> temp1 = dfs(A, n-1, capacity, dp); // leave

    if(capacity - A[n-1] >= 0) {

        pair<int, int> a2 = dfs(A, n-1, capacity-A[n-1], dp); // pick
        pair<int, int> temp2 = {
            A[n-1] + a2.first,
            1 + a2.second
        };

        dp[n][capacity] = compare(temp1, temp2);        

    } else {
        dp[n][capacity] = temp1;
    }

    return dp[n][capacity];    
}


int Solution::solve(const vector<int> &A) {

    int n = A.size();
    int sum = 0;

    for(int i=0; i<n; i++) {
        sum += A[i];
    }

    int capacity = sum/2;
    // like every dp problem, it is very important to know what does dp array store?
    // dp[i][j] array stores the maximum sum 
    // that is possible to extract from the first i items of the array not exceeding capacity j.
    // It also stores the minimum count of numbers filled up in the knapsack(aka minimum number of flips) to achieve that maximum sum.
    vector<vector<pair<int, int>>> dp(n+1, vector<pair<int, int>> (capacity+1, {-1, -1}));
    pair<int, int> ans = dfs(A, n, capacity, dp);

    // cout << capacity << endl;
    // cout << ans.first << endl;
    return ans.second;
}

Answer 3

For determining the minimum non-negative sum of all elements after flipping the sign, we will flip the sign of all the elements that come into the Knapsack. By doing this, we indirectly calculate the sum of all the elements in the Knapsack as close to S/2 as possible. To solve the problem, we need to think deeply and code efficiently.

Our aim is to fill a Knapsack of capacity (S/2) with the minimum number of elements and as fully as possible. To accomplish this, we will use the given elements.

public class Solution {
    public int solve(final int[] A) {
        int N = A.length;
        
        // 105 is total items can present in array
        // 10005 sum can reach to this
        Node [][]dp = new Node[105][10005];

        int sum = 0;
        for (int i = 0; i < N; i++) 
            sum += A[i];


        for (int i = 0; i < 105; i++)
            for (int j = 0; j < 10005; j++) 
                dp[i][j] = new Node(0, 0);

        int temp = sum / 2;

        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= temp; j++) {
                 if (i == 0 || j == 0) {
                     dp[i][j] = new Node(0,0);
                 } else {
                    int prev_items = dp[i - 1][j].item;
                    int prev_weight = dp[i - 1][j].weight;

                    if (j - A[i - 1] >= 0) {
                        int curr_weight = dp[i - 1][j - A[i - 1]].weight + A[i - 1];
                        int curr_items = dp[i - 1][j - A[i - 1]].item + 1;

                        if ((curr_weight > prev_weight) || ((curr_weight == prev_weight) && (curr_items < prev_items))) {
                            dp[i][j] = new Node(curr_items, curr_weight);
                        } else {
                            dp[i][j] = dp[i - 1][j];
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                 }
            }
        }

        return dp[N][temp].item;
    }
}

class Node {
    int item;
    int weight;

    Node(int item, int weight) {
        this.item = item;
        this.weight = weight;
    }
}

Answer 4

int minimum(int a,int b){
    if(a>b) return b;
    else return a;
}
int Solution::solve(const vector<int> &A) {
    int sum = 0;
    vector<int> AN;
    for(int i = 0;i<A.size();i++){
        sum = sum + A[i];
        AN.push_back(A[i]);
    }
    int n = A.size();
    sort(AN.begin(),AN.end());
    int Answer[n+1][sum+1];
    for(int i = 0;i<=n;i++){
        Answer[i][0] = 0;
    }
    for(int i = 1;i<=sum;i++){
        Answer[0][i] = -1;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=sum;j++){
            if(AN[i-1]==j){
                Answer[i][j] = 1;
            }
            else{
                if(j<AN[i-1]){
                    Answer[i][j] = Answer[i-1][j];
                    // cout<< Answer[i][j] <<endl;
                }else{
                    int first = Answer[i-1][j];
                    
                    int second = Answer[i-1][j-AN[i-1]];
                    
                    if(first != -1 && second != -1){
                        second = second + 1;
                        Answer[i][j] = minimum(first,second);
                    }
                    if(first == -1 && second != -1){
                        Answer[i][j] = second + 1;
                    }
                    if(first != -1 && second == -1){
                        Answer[i][j] = first;
                    }
                    if(first == -1 && second == -1){
                        Answer[i][j] = - 1;
                    }
                }
            }
        }
    }
    
    int MIN = 0;
    for(int j = sum/2;j>=0;j--){
        if(Answer[n][j]>0){
            MIN = Answer[n][j];
            break;
        }
    }
    return MIN;
}

Answer 5

The solution given in the GFG is very ambiguous to me also, but I found out this solution which I tried to comment heavily and hope that everyone understands it Below is the intuition

Let the sum of all the given elements be S. This problem can be reduced to a Knapsack problem where we have to fill a Knapsack of capacity (S/2) as fully as possible and using the minimum no. of elements. We will fill the Knapsack with the given elements. Sign of all the elements which come into the knapsack will be flipped. As sum of all the elements in the Knapsack will be as close to S/2 as possible, we are indirectly calculating minimum non-negative sum of all the elements after flipping the sign

    int Solution::solve(const vector <int>&A) {

   int sum=0, n=A.size();
   
   if(n<2) 
      return 0;
   for(int i=0;i<n;i++)
       sum+=A[i];

   sum=sum/2;
   // minimum positive difference that we can obtain by reversing the signs
   // of elements
   //  two equal subset ke hi toh beech me toh minimum difference hoga
   pair<bool,long long> dp[n+1][sum+1];
   // bool state is used here so that to tell particular sum is possible or not 
   // long long has been taken to record the flips that we have done
   // n+1 first dimension is for the number of elements
   // sum+1 is for the current sum that we will get
   
   
   // intialization
   long long int ans=INT_MAX;
   for(int i=0;i<=n;i++)
      dp[i][0]={true,0};// if sum==0 then no flips is needed since it is 
      // minimum possible positive sum as given in question 
      // and no this is obtainable to by taking null set

   for(int i=1;i<=sum;i++)
       dp[0][i]={false,INT_MAX};
       // if no of elements is equal to zero and we need positive sum
       // so it is not possible to get that using any number of elements 
       // since no of elements are 0 and infinite no of flips can also
       // not produce the sum because the no of elements are zero itself 
       
    // knapsack approach
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=sum;j++)
       {
           if(j>=A[i-1]) // if current sum is possible by considering 
           // the current element 
           {
              dp[i][j].first=dp[i-1][j].first||dp[i-1][j-A[i-1]].first;
              if(dp[i][j].first==false)// as said if the sum is not possible 
                 dp[i][j].second=INT_MAX;// so infinite number of flips 
                 // can also not get that sum
               else// had to minimise the number of flips therefore storing minimum 
                  dp[i][j].second=min(dp[i-1][j].second,1+dp[i-1][j-A[i-1]].second);
         
           }// if not possible then store the previous information
           else dp[i][j]=dp[i-1][j];
       
       }
   
   }
int f=0;
for(int i=sum;i>=1;i--)// iterating from backside to get the minimum sum possible
// since we want to divide them into subsets as close to totalsum/2 to minimise 
//difference
{
    for(int j=1;j<=n;j++)
    {
        if(dp[j][i].first==true)// if sum is possible
        {
            ans=min(ans,dp[j][i].second); f=1;// for number of flips
        }
    }
    if(f==1) break;// found subset with closest sum as possible to totalsum/2 therefore
    // we are breaking from here
    
}

return ans;
}