编程题——求正数数组的最小不可组成和(动态规划：01背包问题)

题目描述：


给定一个全是正数的数组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的最小不可组成和。

动态规划：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个状态的最值求出来,这就是动态规划的思想

程序代码如下：