先找到数组中的最小值min,以及元素最大和add;
按照0/1背包问题,我们可以列出如下表格:
j表示组成和也就是背包的容量的组成情况,a[i]表示前i个物品任意选放的最大价值,i表示物品下标,dp[j]表示背包容量为j时,
背包的最大价值(01背包问题可以选择放入物品和不放,只需选择最大价值的那个)
遍历背包数组,直到最后如果可以组成相应背包,那么dp[j]值也就是背包的价值应该和背包此时的容量是一样的,如果有不一样的,
那么第一个出现的就是最小不可组成和
例如:3 2 5
定义一个价值容器:
j 0 1 2 3 4 5 6 7 8 9 10
i a[i]
0 3 0 0 0 3 3 3 3 3 3 3 3
1 2 0 0 2 3 3 5 5 5 5 5 5
2 5 0 0 2 3 3 5 5 7 8 8 10
上面表格中,每一行都是对上一行元素的覆盖更新,从后往前放,用低价值更新高价值
public static int getFirstUnFormedNum(int[] arr) { int minSum=Integer.MAX_VALUE; int maxSum=0; for(int i = 0; i < arr.length; i++){ if(minSum>arr[i]){ minSum = arr[i]; } maxSum+=arr[i]; } int[]dp=new int[maxSum+1]; dp[0]=0; for(int i = 0;i<arr.length; i++){ for(int j=maxSum;j >=arr[i];--j) { //对于背包容量小于物品重量的直接跳过,肯定是装不下的 dp[j]=Math.max(dp[j-arr[i]]+arr[i],dp[j]); //对于01背包问题,存在取和不取的情况,取一个最大值即可 } } for(int j=minSum;j<=maxSum;j++){ if(dp[j]!=j){ return j; } } return maxSum+1; }
😀😀