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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//输入商品个数
        int Max_room = scanner.nextInt();//输入袋子容量
        int[] weight = new int[n];
        int[] price = new int[n];
        int i = 0;
        while (i < n)
            weight[i++] = scanner.nextInt();
        i = 0;
        while (i < n)
            price[i++] = scanner.nextInt();
        int[][] dp = new int[n + 1][Max_room + 1];

        for (i = 1; i <= n; i++) {
            for (int j = 1; j <= Max_room; j++) {
                if (weight[i - 1] > j) {//袋子的容量不够
                    dp[i][j] = dp[i - 1][j];
                } else {//袋子容量足够
                    dp[i][j] = Math.max(dp[i - 1][j], price[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
            }
        }
        System.out.println(dp[n][Max_room]);
    }

    public static int getFirstUnFormedNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {//只有一个元素 ，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和；
            return arr[0] + 1;
        }
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max += arr[i];
            min = Math.min(arr[i], min);
        }
        int[] dp = new int[max + 1];


        for (int i = 0; i <arr.length ; i++) {
            for (int j = max; j >= arr[i]; j--) {
                //dp数组从后向前赋值
                dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
            }
        }

        for (int i = min; i < max; i++) {
            if (dp[i] != i)
                return i;
        }
        return max + 1;
    }

import java.util.*;
public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
    public void getNumber(int[] arr,ArrayList<Integer> result,int pos,int sum){
        if(pos==arr.length){
            return;
        }
        for(int i = pos;i<arr.length;i++){
            sum += arr[i];
            result.add(sum);
            getNumber(arr,result,i+1,sum);
            sum -= arr[i];
        }
    }
	public int getFirstUnFormedNum(int[] arr) {
         //2种情况: 1.[min,max] 有正数不能被子集相加得到! 返回该 数
         //        2.[min,max] 所以正数都能被子集相加得到 返回 max+1
        Arrays.sort(arr);
        int min = arr[0];
        int max = arr[0];
        ArrayList<Integer> result = new ArrayList<>();
        getNumber(arr,result,0,0);
        for(int i = 1;i<arr.length;i++){
            max += arr[i];
        }
        for(int i = min+1;i<max;i++){
            if(!result.contains(i)){
                return i;
            }
        }
        return max+1;
	}
}

public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
	public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0;i < arr.length;i++){
            if(arr[i] < min){
                min = arr[i];
            }
            max += arr[i];
        }
        int[] dp = new int[max + 1];
       for(int i = 0;i < arr.length;i++){
            for(int j = max;j >= min;j--){
                if(j >= arr[i]){
                    dp[j] = Math.max(dp[j],dp[j - arr[i]] + arr[i]);
                }
            }
        }
        for(int i = min;i <= max;i++){
            if(dp[i] != i){
                return i;
            }
        }
        return max + 1;
	}
}

public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
	public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0;i < arr.length;i++){
            if(arr[i] < min){
                min = arr[i];
            }
            max += arr[i];
        }
        boolean[] res = new boolean[max + 1];
        res[0] = true;
        for(int t : arr){
            for(int i = max;i >= t;i--){
                res[i] = res[i] || res[i - t];
            }
        }
        for(int j = min;j < res.length;j++){
            if(!res[j]){
                return j;
            }
        }
        return max + 1;
	}
}

public class Solution {               public int getFirstUnFormedNum(int[] arr) {
        
        if(arr == null || arr.length == 0)
            return 1;
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max += arr[i];
            min = Math.min(min,arr[i]);
        }

        boolean form[] = new boolean[max + 1];
        form[0] = true; // 为了使单个元素去求和时是真的  (i + 0 = i)
        for (int i = 0; i < arr.length; i++) {
            for (int j = max; j >= arr[i]; j--) {
                form[j] = form[j - arr[i]] || form[j];
            }
        }

        for (int i = min; i < form.length; i++) {
            if(!form[i])
                return i;
        }

        return max + 1;     }
}