最大体积

题目描述算法训练  最大体积

时间限制：1.0s     内存限制：256.0MB

问题描述

每个物品有一定的体积（废话），不同的物品组  合，装入背包会战用一定的总体积。

假如每个物品有无限件可用，那么有些体积是永远也装不出来的。

为了尽量装满背包，附中的OIER想要研究一下物品不能装  出的最大体积。

题目保证有解，如果是有限解，保证不超过2，000，000，000 　　如果是无限解，则输出0

输入格式

第一行一个整数n（n< =10），表示物品的件数

第2行到N+1行:  每件物品的体积(1< =  < =500)

输出格式

一个整数ans，表示不能用这些物品得到的最大体积。

样例输入

3 3 6 10

样例输出

17

#include
#include
using namespace std;
int b[600];//储存物品
int ac[10000];//储存可以达到的体积
int n;
int gcd(int a,int b)
{
    if(a%b==0)
    return b;
    return gcd(b,a%b);
}
int GCD()
{
    int r=b[0];
    for(int i=1;i!=n;i++)
    {
        r=gcd(r,b[i]);
    }
    return r;
}
int main()
{
    cin>>n;
    for(int i=0;i!=n;i++)
    {
        cin>>b[i];
        ac[b[i]]=1;//将可以达到的体积标记
    }
    sort(b,b+n);
    //如果所有物品的体积的最大公约数不为1，那么肯定有些数的倍数都不可达，那么不存在最大值
    if(GCD()==1)
    {
        int start=b[n-1];//答案肯定比最大物品的体积大
        int sum=0;
        int i;
        for(i=start+1;i!=10000;i++)//从这10000中找答案
        {
            int j;
            for(j=0;j!=n;j++)
            {
                if(ac[i-b[j]])
                {
                    ac[i]=1;
                    sum++;
                    break;
                }
            }
            if(j==n)sum=0;
            if(sum>b[0])break;
            //就这样一直递推，直到连续出现了一串体积都可以到达了，
            //并且这一串体积的个数大于我们物体的最小体积，
            //说明我们已经可以使用一系列组合实现组合出任意大小物体的能力了
            //那么我们不能到达的体积就在这一串之前那个了。
        }
        cout<<i-sum<<endl;
    }
    else
    {
        cout<<0<<endl;
    }
    return 0;
}