问题描述
每个物品有一定的体积（废话），不同的物品组 合，装入背包会战用一定的总体积。假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，附中的OIER想要研究一下物品不能装 出的最大体积。题目保证有解，如果是有限解，保证不超过2，000，000，000
如果是无限解，则输出0
如果是无限解，则输出0
输入格式
第一行一个整数n（n<=10），表示物品的件数
第2行到N+1行: 每件物品的体积(1<= <=500)
第2行到N+1行: 每件物品的体积(1<= <=500)
输出格式
一个整数ans，表示不能用这些物品得到的最大体积。
样例输入
3
3
6
10
3
6
10
样例输出
17
个人觉得这道题的测评似乎有一点问题，我的测试只通过了90%，只有输入1 1的时候，我的程序自己调试时输出0没问题，但在他那里却报运行错误
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
int gcd(int a,int b){
if(b==)return a;
return gcd(b,a%b);
}
int N,a[];
bool isRight(){
for(int i=;i<N;i++){
for(int j=i+;j<=N;j++){
int s=gcd(a[i],a[j]);
if(s!=a[i]&&s!=a[j]) return ;
}
}
return ;
}
set<long> dp;
bool canFind(long n){
for(int i=;i<=N;i++){
if(n>=a[i]&&!dp.count(n-a[i])) {
return ;
}
}
return ;
}
int main(){
cin>>N;
for(int i=;i<=N;i++){
cin>>a[i];
}
if(!isRight()){
cout<<""<<endl;
return ;
}
sort(a+,a+N+);
queue<long> q; for(int i=;i<a[];i++){
dp.insert(i);q.push(i);
} long ans=;
while(!q.empty()){
long top=q.front();q.pop();
ans=max(top,ans);
for(int i=;i<=N;i++){
if(!dp.count(top+a[i])&&canFind(top+a[i])){
dp.insert(top+a[i]);
q.push(top+a[i]);
}
}
}
cout<<ans<<endl;
return ;
}