正数数组的最小不可组成和

短命女 2022-05-27 01:23 100阅读 0赞

![20180409130733145][]

import java.util.*;
    //正数数组的最小不可组成和
    public class getMinSumArr{
    	
        //返回最小的不可组成和
    
        //(1)暴力递归法(收集每个子集的累加和，存到一个哈希表中)
        public static int getMinSumArr01(int[]arr)
        {
             if(arr==null||arr.length==0)
             {
             	 return 1;
             }
            HashSet<Integer>set=new HashSet<Integer>();
            process(arr,0,0,set); //收集所有的子集和
            int min=Integer.MAX_VALUE;
            for(int i=0;i!=arr.length;i++)
            {
            	 min=Math.min(min,arr[i]);
            }
            for(int i=min+1;i!=Integer.MIN_VALUE;i++)
            {
            	  if(!set.contains(i))
            	  {
            	  	 return i;
            	  }
            }
        	return 0;
        }
        public static void process(int[]arr,int i,int sum,HashSet<Integer>set)
        {
        	  if(i==arr.length)
        	  {
        	  	  set.add(sum);
        	  	  return;
        	  }
        	  process(arr,i+1,sum,set); //包含当前数arr[i]的情况
        	  process(arr,i+1,sum+arr[i],set); //不包含当前数arr[i]的情况
        }
    
    
        //(2)动态规划法
        public static int getMinSumArr02(int[]arr)
        {
        	  if(arr==null||arr.length==0)
        	  {
        	  	 return 1;
        	  }
        	  int sum=0;
        	  int min=Integer.MAX_VALUE;
        	  for(int i=0;i!=arr.length;i++)
        	  {
        	  	  sum+=arr[i];
        	  	  min=Math.min(min,arr[i]);
        	  }
        	  //动态规划数组
        	  boolean []dp=new boolean[sum+1];
        	  dp[0]=true;
        	  for(int i=0;i!=arr.length;i++)
        	  {
        	  	   for(int j=sum;j>=arr[i];j--)
        	  	   {
        	  	   	    dp[j]=dp[j-arr[i]]?true:dp[j];
        	  	   }
        	  }
        	  for(int i=min;i!=dp.length;i++)
        	  {
        	  	  if(!dp[i])
        	  	  {
        	  	  	 return i;
        	  	  }
        	  }
        	  return sum+1;
        }
    //****************************************************
        //进阶问题
        public static int getMinSumArr03(int[] arr) {
    		if (arr == null || arr.length == 0) {
    			return 0;
    		}
    		Arrays.sort(arr); // 把arr排序
    		int range = 0;
    		for (int i = 0; i != arr.length; i++) {
    			if (arr[i] > range + 1) {
    				return range + 1;
    			} else {
    				range += arr[i];
    			}
    		}
    		return range + 1;
    	}
    
    	public static void main(String[]args)
    	{
    
    		//System.out.println("Hello");
    		int[]arr={3,2,5};
    		int[]arr2={1,2,4};
            System.out.println(getMinSumArr01(arr));
            System.out.println(getMinSumArr01(arr2));
            System.out.println(getMinSumArr02(arr2));
            System.out.println(getMinSumArr03(arr2));
    
    
    	}
    }

![20180409130802672][]

[20180409130733145]: /images/20220527/da29b06babcf4637aa7c8db29da1776c.png
[20180409130802672]: /images/20220527/e64a27116fb64ea9b019d02fdad69b12.png