第24章 背包问题进阶

1、整数划分

算法1

完全背包求方案数问题

image.png

时间复杂度

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[] f = new int[N];
    static int mod = 1000000000 + 9;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T -- > 0)
        {
            int n = scan.nextInt();
            Arrays.fill(f, 0);
            f[0] = 1;
            for(int i = 1;i <= n;i ++)
            {
                for(int j = i;j <= n;j ++)
                    f[j] = (f[j] + f[j - i]) % mod;
            }
            System.out.println(f[n]);
        }
        
    }
}

算法2

image.png

时间复杂度

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[][] f = new int[N][N];
    static int mod = 1000000000 + 9;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T -- > 0)
        {
            int n = scan.nextInt();
            for(int i = 0;i <= n;i ++) Arrays.fill(f[i], 0);
            f[1][1] = 1;
            for(int i = 2;i <= n;i ++)
            {
                for(int j = 1;j <= i;j ++)
                {
                    f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
                }
            }
            int ans = 0;
            for(int i = 1;i <= n;i ++)  ans = (ans + f[n][i]) % mod;
            System.out.println(ans);
        }
        
    }
}

2、猫狗大战

3、货币系统

算法分析

若两个货币系统等价，有如下性质

• 性质1：a1,a2,...,an一定都可以被表示出来

• 性质2：在最优解中,b1,b2,...bm一定都是从a1,a2,...,an中选择的

• 性质3：b1,b2,...,bm一定不能被其他bi表示出来

步骤
由于数据中不存在负数，将a[]数组从小到大排序

• (1)若ai能被a0~a(i-1)表示出来，则一定不选

• (2)若ai不能被能被a0~a(i-1)表示出来，则一定选

时间复杂度

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110,M = 25010;
    static boolean[] f = new boolean[M];
    static int[] a = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T -- > 0)
        {
            int n = scan.nextInt();
            for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
            Arrays.fill(f, false);
            Arrays.sort(a,0,n);
            f[0] = true;
            int res = 0,m = a[n - 1];
            for(int i = 0;i < n;i ++)
            {
                if(!f[a[i]]) res ++;
                for(int j = a[i];j <= m;j ++)
                {
                    f[j] |= f[j - a[i]];
                }
            }
            System.out.println(res);
        }
        
    }
}