算法分析

买不到的数目 + 完全背包

根据买不到的数目 可知，体积最大是100，因此不能凑出的最大的数是N = (99 - 1) * (100 - 1) - 1,即最大体积是N

• 1、判断给定的所有数最大公约数是否是1，若不是则返回INF

• 2、若是，

  • 状态表示

  • f[i][j] 表示：是否能从前i个物品中选,且能恰好能凑出体积是j

  • 状态计算

  • f[i][j] = f[i - 1][j] || f[i - 1][j - v] || f[i - 1][j - 2v]...

时间复杂度 $O(N^2)$

Java 代码

import java.util.Scanner;

public class Main {
    static int N = (99 - 1) * (100 - 1) - 1 ;
    static int n;
    static int[] v = new int[101];
    static boolean[] f = new boolean[N + 10];
    static int gcd(int a,int b)
    {
        return b == 0 ? a : gcd(b,a % b);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();

        for(int i = 1;i <= n;i ++) 
        {
            v[i] = scan.nextInt();
            f[v[i]] = true;
        }

        int c = v[1];
        for(int i = 2;i <= n;i ++) c = gcd(c,v[i]);

        if(c == 1)
        {   
            for(int i = 1;i <= n;i ++)
                for(int j = v[i];j <= N;j ++)
                {
                    f[j] = f[j] || f[j - v[i]];
                }
            int res = 0;
            for(int i = 1;i <= N;i ++)
            {
                if(!f[i]) res ++;
            }
            System.out.println(res);
        }
        else System.out.println("INF");
    }
}