2. 完全背包

背包问题_3.pdf

Acwing 3. 完全背包问题

完全背包，不超过，最大价值
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
00输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

二维版本

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt(), w = sc.nextInt();
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k * v <= j; k++)
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v] + k * w);
            }
        }
        System.out.println(f[n][m]);
    }
}

优化掉枚举**k**的过程

1. f[i, j] 表示只从前i个物品中选，且总体积不超过v的所有选法的集合，其属性是价值最大值
2. 状态计算：只考虑前i件物品的情况下计算在所有体积下的选法的最大价值

f[i, j] = max(f[i - 1][j], f[i, j - v[i]] + w[i]

1. 初始状态

当 i == 0时，意思是从前0件物品中选且总体积不超过j的最大价值，很显然，结果是0
Arrays.fill(f[0], 0) 可写可不写。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] f = new int[n + 1][m  + 1];
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt(), w = sc.nextInt();
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= v)
                    f[i][j] = Math.max(f[i][j], f[i][j - v] + w);
            }
        }
        System.out.println(f[n][m]);
    }
}

一维优化

带枚举物品数的遍历，j得从大到小遍历

import java.util.*;
public class Main {
    static final int N = 1010;
    static int[] f = new int[N];
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt(), w = sc.nextInt();
            for (int j = m; j >= v; j--) {
                for (int k = 0; k * v <= j; k++) {
                    f[j] = Math.max(f[j], f[j - k * v] + k * w);
                }
            }
        }
        System.out.println(f[m]);
    }
}

不带枚举物品数的遍历，与01背包正好相反，体积j从小到大枚举

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] f = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt(), w = sc.nextInt();
            for (int j = v; j <= m; j++)
                f[j] = Math.max(f[j], f[j - v] + w);
        }
        System.out.println(f[m]);
    }
}

完全背包求方案数

AcWing 1023. 买书
完全背包，恰好装满，方案数
思路：
状态表示：f[i][j]表示从前i个物品中选，总价格恰好为j的所有选法的集和
状态属性：集和元素个数
状态转移：考虑第i个数选或不选，如果选的话，选几个
f[i][j] += f[i - 1][j] + f[i][j - v]
初始化：f[0][0] = 1表示什么也不选也是一种方案

import java.util.*;
public class Main {
    static final int N = 4, M = 10010;
    static int[][] f = new int[N + 1][M];
    static int[] a = {0, 10, 20, 50, 100};
    public static void main(String[] args) {
        var sc =  new Scanner(System.in);
        int m = sc.nextInt();
        f[0][0] = 1;
        for (int i = 1; i <= 4; i++) {
            int x = a[i];
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= x)
                    f[i][j] += f[i][j - x];
            }
        }
        System.out.println(f[N][m]);
    }
}

// 优化掉物品维
import java.util.*;
public class Main {
    static int N = 4, M = 1010;
    static int[] f = new int[M];
    static int m;
    static int[] a = new int[]{0, 10, 20, 50, 100};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        f[0] = 1;
        for (int i = 1; i <= N; i++) {
            int x = a[i];
            for (int j = x; j <= m; j++)
                f[j] += f[j - x];
        }
        System.out.println(f[m]);
    }
}

其它例题