题目描述：
-
小虎是游戏中的一个国王，在他管理的国家中发行了很多不同面额的纸币，用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天，他突然很想知道这些纸币的组合不能表示的最小面额是多少，请聪明的你来帮助小虎来解决这个财政问题吧。
- 输入：
-
输入包含多个测试用例，每组测试用例的第一行输入一个整数N（N<=100）表示流通的纸币面额数量，第二行是N个纸币的具体表示面额，取值[1，100]。
- 输出：
-
对于每组测试用例，输出一个整数，表示已经发行的所有纸币都不能表示的最小面额（已经发行的每个纸币面额最多只能使用一次,但面值可能有重复）。
- 样例输入：
-
5 1 2 3 9 100 5 1 2 4 9 100 5 1 2 4 7 100
- 样例输出：
-
7 8 15
仔细分析其实该题是变相的01背包动归题。包的最大容量可以看成所有货币加起来的总和。例如第一组数据1,2,3,9,100，那么sum=115，那么我们把他转化为01背包的问题来思考-->即背包容量从115变到1时，求前5个物品在每一个容量下，是否可以满载背包，即把背包装满。若在某种背包容量下，求出的最大值==sum，即满足题设，若求出的最大值<sum,即没有将背包装满，也表示这个货币没法构成。其实就是背包问题恰好装满的情况。
自己还是对动归的01背包问题没有掌握透彻，动态规划解题可以用递归，递推。很明显递归思路清晰，但时间复杂度高，而递推是从树结构的底部逐渐求到最顶部，并且把每一次循环的结果保存到dp数组中.
ps：dp数组既可以是二维，也可以使一维，因而也衍生出了很多的问题。具体参见blog：http://blog.csdn.net/insistgogo/article/details/8579597
1.深搜法：
我首先用了穷举法，把所有的状态都列举出来。即求出从N个数字中任意选取k(1=<k<=N)个的所有序列的和。那么一共就有2N个状态，因为对每一个数字都有两种选择。那么所有的和求出来之后，我们只需要一个hash数组，以sum为角标去标记该sum是否出现过，即hash[sum]=1表示出现了该sum。最后遍历sum数组，找出最早hash[i]!=1的那个i角标，即为解。//深搜，超时
void dfs(int i,int sum) { my_Hash[sum]=1; if(i==myN) { return; } //不加第0个数的值 dfs(i+1,sum); //加第0个数的值 dfs(i+1,sum+coin_val[i]); return; }
2.dp法：int solve58() { memset(dp,0,sizeof(dp)); //容量为N个货币加起来的值:sum，物品个数：N for (int i=1;i<=N;++i) { for (int j=sum;j>=coin_val[i];--j) { dp[j]=max(dp[j],dp[j-coin_val[i]]+coin_val[i]);//物品的体积也即物品的价值。 } } for (int i=1;i<=sum;++i) { if(dp[i]!=i) return i;
九度上的动态规划题：