首页 > 试题广场 >

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

[编程题]求正数数组的最小不可组成和
  • 热度指数:3557 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个全是正数的数组arr,定义一下arr的最小不可组成和的概念: 1,arr的所有非空子集中,把每个子集内的所有元素加起来会出现很多的值,其中最小的记为min,最大的记为max; 2,在区间[min,max]上,如果有一些正数不可以被arr某一个子集相加得到,那么这些正数中最小的那个,就是arr的最小不可组成和; 3,在区间[min,max]上,如果所有的数都可以被arr的某一个子集相加得到,那么max+1是arr的最小不可组成和; 举例: arr = {3,2,5} arr的min为2,max为10,在区间[2,10]上,4是不能被任何一个子集相加得到的值中最小的,所以4是arr的最小不可组成和; arr = {3,2,4} arr的min为2,max为9,在区间[2,9]上,8是不能被任何一个子集相加得到的值中最小的,所以8是arr的最小不可组成和; arr = {3,1,2} arr的min为1,max为6,在区间[2,6]上,任何数都可以被某一个子集相加得到,所以7是arr的最小不可组成和; 请写函数返回arr的最小不可组成和。
0,1背包问题,时间复杂度O(n*max)
int getFirstUnFormedNum(vector<int> arr, int len) {      
int i,j;          
int mi = arr[0],sum = 0;          
for (i = 0;i<len;i++)          
{              
sum sum  +=  arr [ i ];              
if   ( arr [ i ]< mi )                  
mi  =  arr [ i ];          
}          
vector <int>  dp ( sum + 1 , 0 );          
for   ( =   0 ; i < len ; i ++)              
for   ( =  sum ; j >= arr [ i ]; j --)              
{                  
if   ( dp [ j - arr [ i ]]+ arr [ i ]> dp [ j ])                      
dp [ j ]   =  dp [ j - arr [ i ]]+ arr [ i ];                  
else                      
dp [ j ]   =  dp [ j ];              
}          
for   ( =  mi ; i <= sum ; i ++)          
{              
if   ( !=  dp [ i ])                
return  i ;          
}          
return  i ;      
}
编辑于 2015-03-11 14:46:23 回复(4)

动态规划: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

编辑于 2019-07-12 19:45:57 回复(0)
题目很坑地没有给出数据范围,如果数据大优化要麻烦得多,这对考虑周全的人很不利。。(虽然我不是。。)


#include <set>
#include <vector>
using namespace std;
class Solution {
public:
 /**
 *	正数数组中的最小不可组成和
 *	输入:正数数组arr
 *	返回:正数数组中的最小不可组成和
 */
 int getFirstUnFormedNum(vector<int> arr, int len) {
 set<int> S;
        vector<int> tmp;
        int mi = 0x7fffffff;
        for(int i = 0; i < len; ++i) {
            if(arr[i] <  mi) mi = arr[i];
            for(set<int>::iterator it = S.begin(); it != S.end(); ++it) tmp.push_back(*it + arr[i]);
            for(unsigned int i = 0; i < tmp.size(); ++i)S.insert(tmp[i]);
            S.insert(arr[i]);
            tmp.clear();
        }
        for(int i = mi; ; ++i) if(S.find(i) == S.end()) return i;
        return -1;
    }
};

编辑于 2015-03-12 10:44:21 回复(1)
这是一个动态规划的01背包问题;
根据承重和已有的重量种类阶段性计算当前承重时能够放入的重量
当数组中只有2重量的时候,背包承重从2-10都可以放入2的数值
当数组中放入2和3重量的时候,背包承重从5-10
可以放入5,3-4放入3,2只能放入2
当数组中放入2,3,5重量时,背包承重10放入10,8-9放入8,7放入7,5-6
放入5...
class Solution {
public:
	/**
	 *	正数数组中的最小不可组成和
	 *	输入:正数数组arr
	 *	返回:正数数组中的最小不可组成和
	 */
	int getFirstUnFormedNum(vector<int> arr, int len) {
        int sum = 0, min = arr[0];
        for(int i = 0; i < len; ++i){
            sum += arr[i];
            min = min < arr[i] ? min : arr[i];
        }
        vector<int> v(sum + 1, 0);
        for(int i = 0; i < len; ++i){
            //{2, 3, 5}
            //i=0--d[10]=2 d[9]=2 d[8]=2 d[7]=2...d[2]=2
            //i=1--d[10]=5 d[9]=5...d[5]=5 d[4]=3 d[3]=3
            //i=2--d[10]=10 d[9]=8 d[8]=8 d[7]=7 d[6]=5 d[5]=5
            for(int j = sum; j >= arr[i]; --j){
                //逆序判断背包承重中能够放入的数据
                //当数组中只有2的时候,背包承重从2-10都可以放入2的数值
                //当数组中放入2和3的时候,背包承重从5-10可以放入5,3-4放入3,2只能放入2
                //当数组中放入2,3,5时,背包承重10放入10,8-9放入8,7放入7,5-6放入5...
                //dp[j-arr[i]]意思是背包承重为j时,如果已经放置了arr[i]的重量后还能放置的最大重量
                if(v[j] < v[j - arr[i]] + arr[i]){
                    v[j] = v[j - arr[i]] + arr[i];
                }
            }
        }
        //最后当承重为n时,放入的重量不为n则认为是最大不可求和
        for(int i = min; i <= sum; ++i){
            if (i != v[i]){
                return i;
            }
        }
        return sum + 1;
    }
};

发表于 2020-07-16 19:09:21 回复(0)
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;
    }
};

编辑于 2023-02-11 17:21:39 回复(0)
class Solution {
public:
    /**
     *    正数数组中的最小不可组成和
     *    输入:正数数组arr
     *    返回:正数数组中的最小不可组成和
     */
    int getFirstUnFormedNum(vector<int> arr, int len) {
         int min=arr[0]; //1.找到min,max
         int max = 0;
        for(auto e:arr)
        {
           if(min>e)
               min = e;
            max +=e;
        }
        
        unordered_map<int,int> dp; //初始化
        
        for(int i=0;i<arr.size();i++) //将东西依次放入背包
        {
            for(int j=max;j>=arr[i];j--) //从最大值先开始。依次dp判断,取最大值
            {
                 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;
    }
};
发表于 2022-11-02 21:01:57 回复(0)
import java.util.*;
public class Solution {
    /**
     *    正数数组中的最小不可组成和
     *    输入:正数数组arr
     *    返回:正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
       //只有一个元素 直接返回不可合成数为此元素+1
        if(arr.length==1)
            return arr[0]+1;
        
        int sum=0;//最大合成数即集合所有元素相加
        int min=Integer.MAX_VALUE;//最小合成数即集合最小元素
        for(int a:arr)
        {
            sum+=a;
            if(a<min)
                min=a;
        }
        //动态规划 类背包问题
        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]||dp[j-arr[i]];//上一轮外循环的本位可合成||上一轮外循环的j-arr[i]位可合成 
        }
        for(int i=min+1;i<sum;i++)//sum位和min位免检
        {
            if(!dp[i])
                return i;
        }
        return sum+1;
    }
}
发表于 2022-11-02 13:10:11 回复(0)
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]);
    }


这道题,可以看作是背包问题的变形 背包容量的范围在【min,max】,arr数组相当于每个物品的重量
如果背包容量和所承载的物品重量不相等,就是所求
可以转换的原因是:背包容量[min,max]是数组的子集之和的范围,
比如数组2 3 4,背包从2~9,背包2号承载了子集2的和,背包5就是子集2,3的和,这里的2,3,4就可看作是元素权重,而某一个背包如果不能承载这些权重,就不是子集之和








    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;
    }



编辑于 2022-09-10 00:58:00 回复(0)
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;
	}
}


发表于 2022-05-06 09:41:17 回复(0)
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;
	}
}


编辑于 2022-05-08 11:55:35 回复(0)
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;     } };

发表于 2022-03-25 12:25:24 回复(0)
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;
    }
};

发表于 2021-11-26 23:49:20 回复(0)
public class Solution {
    /**
     *    正数数组中的最小不可组成和
     *    输入:正数数组arr
     *    返回:正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }

        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length;i++){
            max += arr[i];
            min = Math.min(min, arr[i]);
        }
        
        boolean[][] dp = getDp(arr, max);

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

        return max + 1;
    }


    // [0,idx]能否严格组合成target
    private static boolean[][] getDp(int[] arr, int max){
        boolean[][] dp = new boolean[arr.length][max + 1];
        
        // if(target < 0) return false;
        
        
        for(int target = 0; target <= max; target++){
            dp[0][target] = target == arr[0] || target == 0;
        }
        
        for(int idx = 1; idx < arr.length; idx++){
            for(int target = 0; target <= max; target++){
                dp[idx][target] = dp[idx-1][target] || (target - arr[idx] >= 0 ? dp[idx - 1][target - arr[idx]] : false);
            }
        }
        
        return dp;
    }
}
发表于 2021-07-25 16:48:53 回复(0)
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;
    }
}

发表于 2021-07-17 19:54:43 回复(0)
n个元素就是一个子集和,加入新一个元素后,就是前n个元素的所有子集和都加上新的元素,与原来前n个元素的子集和一起,构成了n+1的元素的自己和。
无脑求出所以子集和,然后遍历就行。
优化的话,考虑子集和可能重复,可以选择用set进行排序与去重
class Solution {
public:
	/**
	 *	正数数组中的最小不可组成和
	 *	输入:正数数组arr
	 *	返回:正数数组中的最小不可组成和
	 */
	int getFirstUnFormedNum(vector<int> arr, int len) {
        set<int> s;
		s.insert(arr[0]);
		for (int i = 1; i < len; i++)
		{
			auto it = s.begin();
			set<int> t(s);
			while(it!=s.end())		
				t.insert(*(it++) + arr[i]);
			t.insert(arr[i]);
			s = t;
		}
		auto it = s.begin();
		while (it != --s.end()) {
			int t = *(it++);
			if (*it != t + 1)
				return t + 1;
		}
		return *it + 1;
    }
};



编辑于 2019-12-08 21:47:12 回复(0)
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;
    }
大佬们看一下我这个有啥问题,思路就是把所有的非空子集的和装入set中,然后查找,case通过0
发表于 2019-04-05 18:16:42 回复(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;
    }
}
发表于 2018-03-22 21:51:37 回复(0)

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;     }
}


编辑于 2017-09-18 23:00:12 回复(0)
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;
   }
}

编辑于 2017-09-14 00:09:21 回复(0)
mwq头像 mwq
public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入:正数数组arr
	 *	返回:正数数组中的最小不可组成和
	 */

       //组成和看成背包容量,元素看成重量和价值相等的物品

	public int getFirstUnFormedNum(int[] arr) {
		int max	= arr[0];
		int ret = 0;
		
		for(int i = 1; i < arr.length; i++){
			max += arr[i];
		}
		
		//排序
		for(int i = 0; i < arr.length; i++){
			for(int j = i+1; j < arr.length; j++){
				if(arr[i] > arr[j]){
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		
		int[][] m = new int[max + 1][arr.length];
		int[][] tag = new int[max + 1][arr.length];
		
		for(int i = 0; i < arr[0]; i++){
			for(int j = 0; j < arr.length; j++){
				m[i][j] = 0;
				tag[i][j] = 0;
			}
		}
		
		for(int i = arr[0]; i <= max; i++){
			m[i][0] = arr[0];
			tag[i][0] = 1;
		}
		
		for(int j = 0; j < arr.length; j++){
			m[arr[0]][j] = arr[0];
		}
		int i = 0;
		
		
		for(i = arr[0]+1; i <= max; i++){
			for(int j = 1; j < arr.length; j++){
				m[i][j] = m[i][j-1];
				if(arr[j] <= i){
					if(m[i - arr[j]][j] + arr[j] > m[i][j-1]){
						if(tag[i-arr[j]][j] == 0){
							m[i][j] = m[i - arr[j]][j] + arr[j];
							tag[i][j] = 1;  //背包中放了arr[j],标记为1,否则为0
						}else{
							m[i][j] = m[i-1][j];
						}
					}
					
				}
			}
			
			if(m[i][arr.length-1] != i){
				ret = i;    
				break;
			}
		}
		
		if(i == max + 1){
			ret = max + 1;
		}		
		
		
		return ret;
	}

发表于 2015-07-24 10:44:29 回复(0)