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

动态规划：01背包问题(无物品价值)，思想相同，题目最终要求有些变化

min为最轻物品的重量，sum为所有物品总重量

假设有一个能装入容量为C(C在[min,sum]间取值)的背包和n件重量分别为w1,w2,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，要求输出不满足条件的最小容量。
以数组{3,2,5}为例，dp初始化全为0
接下来进行逆序分析：

(逆序是因为同一件物品只能放一次)
(因为分情况时容量要减去当前物品重量，所以高容量的值要用低容量来更新，可能造成重复放入)
(举个例子，判断3是否放入时，如果是顺序的话dp[3]=dp[3]+3放了一次3,之后dp[6]=dp[3]+3又放了一次，就重复了)

判断某一物品能否放入时直接忽略容量小于该物品质量的情况

先判断3是否放入
对于容量为3及以上的都选择放入，对应dp值更新为3

再判断2是否放入
对于容量为5及以上的都选择放入，加上3，对应dp值更新为5
对于容量为3、4的如果放入后剩余容量不够放其他物品，比较3后选择较大值，对应dp值仍为3
容量为2的选择放入，对应dp值更新为2

最后判断5是否放入
对于容量为10的选择放入，加上5，dp值更新为3
对于容量为9的选择放入，加上3， dp值更新为8
对于容量为8的选择放入，加上3， dp值更新为8
对于容量为7的选择放入，加上2， dp值更新为7
对于容量为6的选择放入，dp值更新为5
对于容量为5的选择放入，dp值更新为5

在前i个状态下的最值的前提下，考虑第i个值是否使用，从而把前i个状态的最值求出来,这就是动态规划的思想

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int getFirstUnFormedNum(vector<int> arr, int len) {
        int sum = 0, min = arr[0];
        for (int i = 0; i < len; ++i)
        {
            sum += arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        vector<int> dp(sum + 1, 0);
        for (int i = 0; i < len; ++i)
        {
            for (int j = sum; j >= arr[i]; --j)
            {
                if (dp[j - arr[i]] + arr[i] > dp[j])
                {
                    dp[j] = dp[j - arr[i]] + arr[i];
                }
            }
        }

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

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        Solution s;
        cout << s.getFirstUnFormedNum(a, n) << endl;
    }
    return 0;
}

原文：https://blog.csdn.net/kevin980123/article/details/95651534

#include <unordered_map>
#include <vector>
using namespace std;
class Solution
{
    public:
    int sum=0;
    void dfs(vector<int>& arr,int begin,int end,unordered_map<int,int>& hash)
    {
        if(begin>=end)return ;
        for(int i=begin;i<end;i++)
        {
            sum+=arr[i];
            hash[sum]++;
            dfs(arr,i+1,end,hash);
            sum-=arr[i];
        }
    }
    int getFirstUnFormedNum(vector<int> arr, int len) {  
        unordered_map<int,int> hash;
        dfs(arr,0,len,hash);
        int minum=0x3f3f3f3f;
        int sum=0;
        for(auto e:arr)
        {
            minum=min(minum,e);
            sum+=e;
        }
        int ret=-1;
        for(int i=minum;i<=sum;i++)
        {
            if(hash.find(i)==hash.end())
            {
                ret=i;
                break;
            }
        }
        if(ret==-1)ret=sum+1;
        return ret;
    }
};

class Solution {
public:     /**      *    正数数组中的最小不可组成和      *    输入：正数数组arr      *    返回：正数数组中的最小不可组成和      */     int getFirstUnFormedNum(vector<int> arr, int len) {
        int min = arr[0];
        int max = 0;
        for(int i = 0; i < len; i++)
        {
            if(arr[i] < min){
                min = arr[i];
            }
            max += arr[i];
        }
        
        vector<int> dp(max+1,0); //背包的大小
        //dp[j]表示背包最大承重(与物品的质量有关)，j表示背包的大小
        for(int i = 0; i < len; i++)
        {
            for(int j = max; j >= arr[i]; j--)
            {
                if(dp[j] < dp[j-arr[i]]+arr[i]){
                    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 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;
	}
}

class Solution {
     vector<vector<int>> result;// 存放所有子集序列
     vector<int>path;// 存放从跟到每个节点
void backtracing(vector<int> v,int startIndex)
    {
        if(!path.empty())
        {
            result.push_back(path);
        }
        if(startIndex>=v.size())
            return;
        for(int i=startIndex;i<v.size();i++)
        {
            path.push_back(v[i]);
            backtracing(v, i+1);
            path.pop_back();
        }
    }
    bool find(int num)
    {
        for(int i=0;i<path.size();i++)
        {
            if(i==num)
                return true;
        }
        return false;
        
    }
  
    
public:
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
  
    
	int getFirstUnFormedNum(vector<int> arr, int len) 
    {
        // 求出vector所有子集
    
        backtracing(arr,0);
        // 将path用来存放所有子集的和
         path.clear();
        for(int i=0;i<result.size();i++)
        {
            int sum=0;
            for(int j=0;j<result[i].size();j++)
            {
                sum+=result[i][j];
            }
            path.push_back(sum);
        }
        //找到子集中的最大值和最小值
        int Max=path[0];
        int Min=path[0];
        for(int i=0;i<path.size()-1;i++)
        {
            Min=min(path[i],Min);
            Max=max(path[i],Max);
        }
        for(int i=Min;i<=Max;i++)
        {
            if(find(i)==0)
            {
                return i;
            }
        }
        return Max+1;
    }
};

class Solution {
public:
    //本题可以转化为 ---> 01背包问题
    //背包容量: 数据组成的范围min ~ max
    //物品:arr的元素
    //1. 确定dp数组
    //dp[j]: 背包容量为j的背包, 背包内所放的物品的总质量是dp[j]
    //2. 状态转移方程:
    //当物品arr[i]能够放入大小为j的背包时 if(arr[i] <= j)
    //dp[j] = max(dp[j], dp[j - arr[i]] + arr[i]);
    //3. 初始化dp数组
    //dp数组开的空间大小为max + 1大小，里面的元素都初始化为0就行
    //4. 确定遍历顺序
    //使用一维滚动数组的话，需要逆序遍历背包，防止元素重复计算
    //使用二维dp的话，先遍历哪个都可以
	int getFirstUnFormedNum(vector<int> arr, int len) 
    {
        //先遍历一遍arr数组求出背包容量的范围[min, max]
        int minSize = INT_MAX, maxSize = 0;
        for(auto e : arr)
        {
            maxSize += e;
            if(minSize > e)
                minSize = e;
        }
        //这里选用了一维dp
        vector<int> dp(maxSize + 1, 0);
        for(int i = 0; i < arr.size(); ++i)
        {
            for(int j = maxSize; j >= minSize; --j)
            {
                if(j >= arr[i])
                    dp[j] = max(dp[j], dp[j - arr[i]] + arr[i]);
            }
        }
        for(int i = minSize; i <= maxSize; ++i)
        {
            if(dp[i] != i)
                return i;
        }
        return maxSize + 1;
    }
};

public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
    public int getFirstUnFormedNum(int[] arr) {
        // 全是正数的 arr
        // i 代表物品
        // j 代表背包容量
        // 目地: 找出数组中最小不可能组成和
        //       ==> 找出最小不能被填满的背包

        // 1. 得到最大最小值
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max += arr[i];
            if (min > arr[i]) {
                min = arr[i];
            }
        }

        // 2. 定义 dp 数组
        boolean[] dp = new boolean[max+1];
        // 初始化
        dp[0] = true;

        // 3. 递推过程
        for (int i = 0; i < arr.length; i++) {
            for (int j = max; j >= arr[i]; j--) {
                // 当 j == arr[i] 的时候, j - arr[i] 代表自己能够到达的下标 2-2 = 0
                // 第一个为 T 的是 3, 当 j == 3 的时候, j - arr[i] = 0;
                // 第二个位 T 的是 5, 当 j == 5 的时候, j - arr[i] = 3;
                // 第三个为 T 的是 2, 当 j == 2 的时候, j - arr[i] = 0;
                // 第四个为 T 的是 9, 当 j == 9 的时候, j - arr[i] = 5;
                // 第五个为 T 的是 7, 但 j == 7 的时候, j - arr[i] = 3;
                // 第六个为 T 的是 6, 当 j == 6 的时候, j - arr[i] = 2;
                // 第七个为 T 的是 4, 当 j == 4 的时候, j - arr[i] = 0;
                dp[j] = dp[j-arr[i]] || dp[j];
                // dp[j-arr[i]] 代表 "拿" 当前数字
                // dp[j] 代表不拿当前数字 比如 5 的时候, dp[5] || dp[5-1] 原来 dp[5] 是 T dp[1] 是 F, 所以这个时候 "不拿"
            }
        }

        // 打印数组
        // System.out.println(Arrays.toString(dp));

        // 4. 查询结果
        for (int i = min; i < dp.length; i++) {
            if (!dp[i]) {
                return i;
            }
        }
        return max + 1;
    }
}

int getFirstUnFormedNum(vector<int> arr, int len) {
        if (len == 0 || arr.size() == 0)             return 1;         set<int> nums;         int sum = 0;         for (int i = 0; i < len; i++)         {             nums.insert(arr[i]);             sum = arr[i];             for (int j = i + 1; j < len; j++)             {                 sum += arr[j];                 nums.insert(sum);
                nums.insert(arr[i] + arr[j]);             }         }         set<int>::iterator itbegin = nums.begin();
        set<int>::iterator itend = nums.end();
        int num = *(--itend);
        for(int k = *itbegin; k < num; k++)
        {
            if(!nums.count(k))
                return k;
        }         return num + 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++) {
            min = Math.min(min, arr[i]);
            max += arr[i];
        }
        boolean[] dp = new boolean[max + 1];
        dp[0] = true;
        dp[arr[0]] = true;
        for (int i = 1;i < arr.length; i++) {
            for (int col = dp.length - 1; col-arr[i] >= 0; col--) {
                dp[col] = dp[col - arr[i]] ? true : dp[col];
            }
        }
        for (int num = min + 1; num <= max; num++) {
            if(! dp[num]) {
                return num;
            }
        }
        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;     }
}

import java.util.*;

public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
   public int getFirstUnFormedNum(int[] arr) {
		int min = Integer.MAX_VALUE;
        int max = 0;
        for(int value: arr){
            if (value < min) min = value;
            max += value;
        }
        Arrays.sort(arr);
        BitSet[] table = new BitSet[arr.length];
        for(int i=0;i<table.length;i++){
            table[i] = new BitSet(max-min+1);
        }


        table[0].set(arr[0]-min);

        for(int i=1;i<arr.length;i++){ //array[i]
            table[i].set(arr[i]-min); //设置当前列的值arr[i],注意偏移
            for(int j=min;j<=max;j++){
                if(table[i-1].get(j-min)){
                    table[i].set(j-min); //继承上一行的值
                    if(j+arr[i]<=max) table[i].set(j+arr[i]-min); //上一行值加上这个值产生的新值
                }
            }
        }

        for(int j=min;j<=max;j++){
            if(!table[arr.length-1].get(j-min)) return j;
        }
        return max+1;
   }
}