|
| 1 | +package DynamicProgramming; |
1 | 2 | // Partition a set into two subsets such that the difference of subset sums is minimum |
2 | 3 |
|
3 | 4 | /* |
|
17 | 18 | import java.util.*; |
18 | 19 | import java.lang.*; |
19 | 20 | import java.io.*; |
20 | | -class GFG |
21 | | - { |
| 21 | +public class MinimumSumPartition |
| 22 | +{ |
22 | 23 | public static void main (String[] args) |
23 | | - { |
24 | | - Scanner sc=new Scanner(System.in); |
25 | | - int t=sc.nextInt(); |
| 24 | + { |
| 25 | + Scanner sc = new Scanner(System.in); |
| 26 | + int t = sc.nextInt(); |
26 | 27 | while(t-->0) |
27 | 28 | { |
28 | | - int n=sc.nextInt(); |
29 | | - int arr[]=new int[n]; |
30 | | - int sum=0; |
31 | | - for(int i=0;i<n;i++) |
| 29 | + int n = sc.nextInt(); |
| 30 | + int arr[] = new int[n]; |
| 31 | + int sum = 0; |
| 32 | + for(int i = 0;i < n;i++) |
32 | 33 | { |
33 | | - arr[i]=sc.nextInt(); |
34 | | - sum+=arr[i]; |
| 34 | + arr[i] = sc.nextInt(); |
| 35 | + sum += arr[i]; |
35 | 36 | } |
36 | | - int ans[]=new int[sum]; |
37 | | - ans=subset(arr,sum); |
38 | | - int min=Integer.MAX_VALUE; |
39 | | - for(int i=0;i<ans.length;i++) |
40 | | - min=Math.min(min,(sum-2*ans[i])); |
| 37 | + int ans[] = new int[sum]; |
| 38 | + ans = subset(arr,sum); |
| 39 | + int min = Integer.MAX_VALUE; |
| 40 | + for (int i = 0; i < ans.length; i++) |
| 41 | + min = Math.min(min,(sum-2*ans[i])); |
41 | 42 | System.out.println(min); |
42 | 43 | } |
43 | 44 | } |
44 | 45 | static int[] subset(int arr[],int sum) |
45 | 46 | { |
46 | | - int n=arr.length; |
47 | | - boolean dp[][]=new boolean[n+1][sum+1]; |
48 | | - for(int i=0;i<=n;i++) |
49 | | - dp[i][0]=true; |
50 | | - for(int i=1;i<=sum;i++) |
51 | | - dp[0][i]=false; |
| 47 | + int n = arr.length; |
| 48 | + boolean dp[][] = new boolean[n+1][sum+1]; |
| 49 | + for(int i = 0; i <= n; i++) |
| 50 | + dp[i][0] = true; |
| 51 | + for(int i = 1; i <= sum; i++) |
| 52 | + dp[0][i] = false; |
52 | 53 | // subset sum concept |
53 | | - for(int i=1;i<=n;i++) |
| 54 | + for(int i = 1; i <= n; i++) |
54 | 55 | { |
55 | | - for(int j=1;j<=sum;j++) |
| 56 | + for(int j = 1; j <= sum; j++) |
56 | 57 | { |
57 | | - if(arr[i-1]<=j) |
58 | | - dp[i][j]=dp[i-1][j-arr[i-1]] || dp[i-1][j]; |
| 58 | + if(arr[i-1] <= j) |
| 59 | + dp[i][j] = dp[i-1][j-arr[i-1]] || dp[i-1][j]; |
59 | 60 | else |
60 | | - dp[i][j]=dp[i-1][j]; |
| 61 | + dp[i][j] = dp[i-1][j]; |
61 | 62 | } |
62 | 63 | } |
63 | 64 | //storing last dp column whose value is true till sum/2 |
64 | | - int index[]=new int[sum]; |
65 | | - int p=0; |
66 | | - for(int i=0;i<=sum/2;i++) |
| 65 | + int index[] = new int[sum]; |
| 66 | + int p = 0; |
| 67 | + for(int i = 0 ; i <= sum / 2; i++) |
67 | 68 | { |
68 | | - if(dp[n][i]==true) |
69 | | - index[p++]=i; |
| 69 | + if(dp[n][i] == true) |
| 70 | + index[p++] = i; |
70 | 71 | } |
71 | 72 | return index; |
72 | 73 | } |
|
0 commit comments