问题描述：
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。
【输入】
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
【输出】一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
【输入输出范例】
输入：
2
4
5
程序应该输出：
6
再例如，
输入：
2
4
6
程序应该输出：
INF
解题思路：
此题是主要是根据蒸笼的种类来组合出能做多少个包子，简单来说将n种数进行组合，每种数个数不限（其实1w差不多了），找到有哪些数是无法组合的，只用统计不能组合出的个数；此题难点就在每种数能拿的个数没有限制，比如（给出3种数：4，5，6）能组合的结果：每个数的倍数，每两个数相加的倍数，三个数相加的倍数，单取数字4，i个再加上5，6，似乎可以组合出很多很多个，穷举不太现实，所以此题用DP来做比较合适，DP主要是解决记住i个数字+其他数字j个 ( 比如：4 * i + 5 * j ( j = 1,2,3...n) ),也节省了当出现相同的数时有不同组合结果的时间 （20 = 4 * 5 or 5 * 4），有点像完全背包，但不完全是，因为这题不是求最优解（价值最大之类的），而是统计不能组成的数有多少，比背包问题简单了一些。
算法设计：
- 用一个dp[ ]来判断这个数能不能组合成,这个数组大小可以给1w，更多也行， 这个范围是求出1~上限，不能组合出的数的个数（我只统计了1~1w的，可以近似理解为无穷大）。
- 数组dp[10000] = { 0 }，0代表不能组成，1表示能组合（其他数都可以），再用一个a[ ]数组存你的原始数（比如你的4，5，6），表达式：( dp[ j - a[ i ] ] == 1 ), j = 1,2,3...n, 相当于用两层循环（最外层循环原始数，内层遍历所有数），当然先把dp[ 0 ] = 1,自己本身肯定能组成，遍历的时候把符合条件的数进行标记，dp[ j ] = 1,这样就能统计出每个数要不同个数时的结果。
- 还要解决一个判断条件，判断是否有无限种不可以组合的情况，从例子中看出：当原始数都是偶数，或者原始数全为某一个数的倍数关系情况下，就有无限种不可能组合出的数。
代码：
#include<stdio.h>
#include<string.h>
#define maxSize 10000
int dp[maxSize];//初始化dp数组，大小自己定（越大越接近无穷）
//判断函数
bool judge(int x, int y)
{
//判断是否全为偶数
//或者候选数全为某一个倍数关系
int t;
while (y > )
{
t = x % y;
x = y;
y = t;
}
if (x == )
return true;
return false;
}
void count(int a[], int n)
{
int res, mark, i, j;
res = ;//计数
mark = ;//判断是否无限的变量
memset(dp, , sizeof(dp));//将数组dp的数全部置为0,不用memset也行，直接dp[10000] = { 0 }
//也对memset主要适用于动态分配内存后的清0手段，其他情况效果差不多
for (i = ; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
if (judge(a[i], a[j]))//每次只能判断两个，所以二层循环遍历所有情况
{
mark = ;
break;
}
}
if (mark == )
break;//只要有一个符合jugde函数就能数出组合的数量
}
if (mark != )
{
printf("INF\n");
return;
}
dp[] = ;//第一个表示候选数的本身，故能组合自己
for (i = ; i <= n; i++)
for (j = ; j < maxSize; j++)
{
//记忆型存储，即时保存之前能组合的数
//输入不分大小，但是要有一定顺序
if (a[i] > j)
continue;//比自己本身还小的数，一定组合不出结果
if (dp[j - a[i]] == )
dp[j] = ;
}
for (i = ; i < maxSize; i++)
{
if (dp[i] != )
res++;//统计不能组合出来数的数量
}
printf("%d\n", res);
}
int main()
{
//小明制作包子问题，蒸笼种类n，每种蒸笼x个包子，统计有多少个包子组合不出来
int a[], n;//数组a可以动态分配
scanf("%d", &n);
count(a, n);
return ;
}
时间复杂度：O(n * maxSize)
如果有更优化的算法，可以指出来，谢谢