根据裴蜀定理可得INF的情况是所有数的最大公约数非1
而我们的完全背包的上限是多少呢?
设置为Σai即可，因为把每一个ai用上之后的集合，和ai可以重复使用的集合，只差了整数倍个ai，因此可达性是完全一致的，这里N<=100,ai<=100，所以我们把这个背包的上限设置为10000.
#include <bits/stdc++.h> using namespace std; int gcd(int m, int n) { if(n) { return gcd(n, m % n); } else { return m; } }//求gcd(m,n),常见的递归写法 const int MAXN = 105, MAX_DP = 100005;//又来定义 int n, a[MAXN], dp[MAX_DP], ans; bool notCoprime(int *arr)//返回arr数组中所有数的最大公约数是否大于1 { int g = arr[0]; for(int i = 1; i < n; i++) { g = gcd(g, arr[i]); if(g == 1) { return false;//如果g已经为1，不用再循环，直接返回 } } return g > 1; }//定义函数，运行更快 int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); }//输入 if(notCoprime(a))//如果gcd({A_i})>1 { printf("INF"); return 0;//直接结束 } dp[0] = 1;//注意0是被认为能被凑出的，否则所有数都凑不出来，循环检查时可以不用从0开始 for(int i = 0; i < n; i++) { for(int j = a[i]; j < MAX_DP; j++) { dp[j] = max(dp[j], dp[j - a[i]]);//状态转移方程 } } for(int i = 1; i < MAX_DP; i++) { if(!dp[i]) { ans++;//如果dp[i]=0,多一个凑不出的数 } } printf("%d", ans);//输出 return 0; }
还有大佬的剩余类最短路做法（可以更好的解释为什么那个完全背包的上限设置为Σai）
#include <queue> #include <cstdio> #include <cstring> #define P pair<int, int> using namespace std; struct E { int v, w, t; } e[10050]; int n, c, z, a[150], d[150], h[150]; bool b[150]; priority_queue<P, vector<P>, greater<P>> q; void A(int u, int v, int w) { e[++c] = {v, w, h[u]}; h[u] = c; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); for (int i = 0; i < a[1]; ++i) for (int j = 2; j <= n; ++j) A(i, (i + a[j]) % a[1], a[j]); memset(d, 0x3f, sizeof d); q.emplace(d[0] = 0, 0); while (!q.empty()) { int u = q.top().second; q.pop(); if (!b[u]) { b[u] = 1; for (int i = h[u], v; i; i = e[i].t) if (d[v = e[i].v] > d[u] + e[i].w) q.emplace(d[v] = d[u] + e[i].w, v); } } for (int i = 0; i < a[1]; ++i) { if (d[i] == 0x3f3f3f3f) return !puts("INF"); z += d[i] / a[1]; } printf("%d", z); return 0; }