【NOIP2012模拟11.6】背包问题

Description 背包问题，是一个流传千古的经典，问题中每个物品有一定的体积，还有一个一定容量的背包。假如每个物品有无限件可用，那么还是有些体积是永远也装不出来的。为了尽量装满背包，小Z要研究一下物品不能装出的最大体积。题目保证有解，如果是是有限解，保证不超过2,000,000,000 如果是无限解或者无解（所有体积都能装出来），则输出0 Input 第一行一个整数n，表示物品的件数 第2行到N+1行: 每件物品的体积v[i] Output 一个整数ans，表示不能用这些物品得到的最大体积。 Sample Input 3 3 6 10 Sample Output 17 Data Constraint Hint n<=10，v[i]<=500

The Solution

这道题应该可以说是一眼题了吧。。。

首先得先判断： 如果输入的那些数的公因数为1，则说明有解，否则无解。证明很显然，就不证了。

然后就可以做个01背包就搞定了

设一个F数组Dp。

预处理F[0]=1， 如果是原来的数字或上0就是它自己即数字本身能达到

CODE

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define fo(i,a,b) for (int i=a;i<=b;i++) #define fd(i,a,b) for (int i=a;i>=b;i--) #define N 50 #define Maxn 100005 using namespace std; int a[N],F[Maxn]; int Gcd(int x,int y) { if (!y) return x; else return Gcd(y,x%y); } int main() { int n; scanf("%d",&n); fo(i,1,n) scanf("%d",&a[i]); int g=a[1]; fo(i,2,n) g=Gcd(g,a[i]); if (g==1) { F[0]=1; fo(i,1,n) fo(j,a[i],65536) F[j]|=F[j-a[i]]; fd(i,65536,0) { if (!F[i]) { printf("%d",i); return 0; } } } printf("0"); return 0; }