給定差值的劃分

給定一個數組‘ARR’，將其劃分為兩個子集（可能為空），這樣它們的並集就是原始數組。設這兩個子集的元素總和為「S1」和「S2」。
給定差“D”，計算“S1”大於或等於“S2”且“S1”和“S2”之間的差等於“D”的分區數。由於答案可能太大，請回傳對‘10^9 + 7’取模的結果。
如果「Pi_Sj」表示分區「i」的子集「j」。然後，如果滿足以下條件，則兩個分區 P1 和 P2 被視為不同：

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 50
0 ≤ D ≤ 2500
0 ≤ ARR[i] ≤ 50

遞歸解：
這將導致 TLE，因為它不是最佳的

import java.util.*;
public class Solution {
    static int mod = (int)(1e9+7);
    public static int countPartitions(int n, int d, int[] arr) {
        // Write your code here.
        /*
        given : 
        1. s1 + s2 = sum; where sum is sum of all the elements in the array
        2. s1-s2 = D for s1>s2;

        modifications: 
        since s1+s2 = sum;hence s1 = sum-s2;
        from 2, 
        sum-s2-s2 = D;
        ie s2 = (sum-D)/2 = target;
        so we have to find all the subsets that are equal to target :)
        edge cases to avoid : 
        1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 
        2. (sum-D)>=0 since it  can't be nagative as sum of all the elements of the array can't be negative
        */
        int target =0;
        for(int i : arr) target+=i;
        //implementing edge case first
        if(target-d<0 || (target-d)%2!=0) return 0;

        return findSubsetSumCountEqualsToTarget(arr,n-1,(target-d)/2);

    }
    public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target){

        if(i==0){
             //since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now ie either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i]);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target);
        return (left+right)%mod;
    }

Dp 記憶解決方案:

//create dp array in the driver class , and add dp to the function call
 int dp[][] = new int[n][(target-d)/2 +1] ;
        for(int row[]: dp) Arrays.fill(row,-1);

public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target,int dp[][]){

        if(i==0){
             //since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now ie either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
         if(dp[i][target]!=-1) return dp[i][target];
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i],dp);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target,dp);
        return dp[i][target] = (left+right)%mod;
    }
}

列表:

import java.util.*;
public class Solution {
    static int mod = (int)(1e9+7);
    public static int countPartitions(int n, int d, int[] arr) {
        // Write your code here.
        /*
        given : 
        1. s1 + s2 = sum; where sum is sum of all the elements in the array
        2. s1-s2 = D for s1>s2;

        modifications: 
        since s1+s2 = sum;hence s1 = sum-s2;
        from 2, 
        sum-s2-s2 = D;
        ie s2 = (sum-D)/2 = target;
        so we have to find all the subsets that are equal to target :)
        edge cases to avoid : 
        1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 
        2. (sum-D)>=0 since it  can't be nagative as sum of all the elements of the array can't be negative
        */
        int target =0;
        for(int i : arr) target+=i;
        //implementing edge case first
        if(target-d<0 || (target-d)%2!=0) return 0;
       return findSolByTabulation(arr,n,(target-d)/2);
    }
    public static int findSolByTabulation(int [] arr, int n, int target){
         int dp[][] = new int[n][target +1] ;
        for(int row[]: dp) Arrays.fill(row,-1);
        if(arr[0] ==0) dp[0][0] = 2;
        else dp[0][0] = 1;
        if(arr[0]!=0 && arr[0]<=target) dp[0][arr[0]]=1;

        for(int i =1;i<arr.length;i++){
            for(int tar = 0;tar<=target;tar++){

                int left =0;
                if(tar>=arr[i]){
                    left = dp[i-1][tar-arr[i]];
                }
                int right = dp[i-1][tar];
                dp[i][tar] = (left+right);
            }

        }
       return dp[n-1][target];

    }
}

以上是給定差值的劃分的詳細內容。更多資訊請關注PHP中文網其他相關文章！