本文共 1393 字，大约阅读时间需要 4 分钟。

完全背包问题的解决方案如下：

问题分析

我们需要找出在给定N个物品的情况下，总体积不超过M的数目中，无法被组合出来的数目。每个物品有特定的体积和价值。通过分析，我们可以使用动态规划来解决这个问题。

方法思路

解决代码

import java.util.Scanner;
public class Main {
    static final int N = 110, M = 10010;
    static int[] a = new int[N];
    static boolean[] f = new boolean[M];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            d = gcd(d, a[i]);
        }
        if (d != 1) {
            System.out.println("INF");
            return;
        }
        f[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = a[i]; j < M; j++) {
                f[j] |= f[j - a[i]];
            }
        }
        int res = 0;
        for (int j = 0; j < M; j++) {
            if (!f[j]) {
                res++;
            }
        }
        System.out.println(res);
    }
    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

代码解释

这种方法确保了在给定约束条件下，正确高效地解决完全背包问题。

转载地址：http://lzhfk.baihongyu.com/