给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max； 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成和； 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 输入例子： 3 3 2 5 输出例子： 2 10 4
public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } sc.close(); int max=a[0],min=a[0]; //最大子集为全集,最小子集为单个元素 for(int i=1;i<n;i++){ max+=a[i]; min=Math.min(min,a[i]); } /* * 对数组的每个元素遍历一遍即可 * 对每个元素判断塞入不同容积的背包背包的大小 * 最终,dp的值为不同的子集组成,若能由子集相加得到,值和序号应该相同 * 给每一个背包塞值，背包最大值就是背包自身 */ int dp[]=new int[max+1];//dp[i]表示容量为i的背包的实际大小 for(int i=0;i<n;i++){ for(int j=max;j>=a[i];j--){ dp[j]=Math.max(dp[j],dp[j-a[i]]+a[i]); } } for(int i=min;i<=max;i++){ if(dp[i]!=i){ System.out.println(min+" "+max+" "+i); return; } } System.out.println(min+" "+max+" "+(max+1)); } }