背包问题_12.pdf

AcWing 11. 背包问题求方案数

01背包，不超过，得到最大价值的所有方案的数量
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示 方案数 模 109+7 的结果。

数据范围
00<vi,wi≤1000

样例
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2

思路：
两种状态定义方式：“恰好”和“不超过”

  • 恰好：
    • f[i][j]表示从前i个物品中选且总体积恰好为j的获得最大价值的选法的集和，属性是最大价值
    • g[i][j]表示从前i个物品中选且总价值为f[i][j]的方案的集和，属性是方案数
    • 初始化：f[i][j] = -INF, f[0][0] = 0, g[0][0] = 1
  • 不超过：
    • f[i][j]表示从前i个物品中选且总体积不超过j的获得最大价值的选法的集和，属性是最大价值
    • g[i][j]表示从前i个物品中选且总价值为f[i][j]的方案的集和，属性是方案数。
    • 初始化：f[i][j] = -INF, f[0][j] = 0, g[0][j] = 1
  1. // 恰好
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 1010, INF = 0x3f3f3f3f, MOD = (int)(1e9 + 7);
  6.     static int[][] f = new int[N][N], g = new int[N][N];
  7.     static int n, m;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  14.         for (int i = 0; i <= n; i++) {
  15.             Arrays.fill(f[i], -INF);
  16.         }
  17.         f[0][0] = 0;
  18.         g[0][0] = 1;
  19.         for (int i = 1; i <= n; i++) {
  20.             int v = sc.nextInt(), w = sc.nextInt();
  21.             for (int j = 0; j <= m; j++) {
  22.                 if (j >= v) {
  23.                     int max = Math.max(f[i - 1][j], f[i - 1][j - v] + w);
  24.                     int cnt = 0;
  25.                     if (f[i - 1][j] == max) cnt += g[i - 1][j];
  26.                     if (f[i - 1][j - v] + w == max) cnt += g[i - 1][j - v];
  27.                     f[i][j] = max;
  28.                     g[i][j] = cnt % MOD;
  29.                 } else {
  30.                     f[i][j] = f[i - 1][j];
  31.                     g[i][j] = g[i - 1][j];
  32.                 }
  34.             }
  35.         }
  37.         int res = 0;
  38.         for (int i = 0; i <= m; i++)
  39.             res = Math.max(res, f[n][i]);
  40.         int cnt = 0;
  41.         for (int i = 0; i <= m; i++)
  42.             if (f[n][i] == res)
  43.                 cnt = (cnt + g[n][i]) % MOD;
  44.         System.out.println(cnt);
  45.     }
  46. }
  49. // 一维
  50. import java.util.*;
  52. public class Main {
  53.     static final int N = 1010, INF = 0x3f3f3f3f, MOD = (int)(1e9 + 7);
  54.     static int[] f = new int[N], g = new int[N];
  55.     static int n, m;
  57.     public static void main(String[] args) {
  58.         Scanner sc = new Scanner(System.in);
  59.         n = sc.nextInt();
  60.         m = sc.nextInt();
  62.         Arrays.fill(f, -INF);
  63.         f[0] = 0;
  64.         g[0] = 1;
  65.         for (int i = 1; i <= n; i++) {
  66.             int v = sc.nextInt(), w = sc.nextInt();
  67.             for (int j = m; j >= v; j--) {
  68.                 int max = Math.max(f[j], f[j - v] + w);
  69.                 int cnt = 0;
  70.                 if (max == f[j]) cnt += g[j];
  71.                 if (max == f[j - v] + w) cnt += g[j - v];
  73.                 f[j] = max;
  74.                 g[j] = cnt % MOD;
  75.             }
  76.         }
  78.         int res = 0;
  79.         for (int i = 0; i <= m; i++)
  80.             res = Math.max(res, f[i]);
  81.         int cnt = 0;
  82.         for (int i = 0; i <= m; i++)
  83.             if (f[i] == res)
  84.                 cnt = (cnt + g[i]) % MOD;
  85.         System.out.println(cnt);
  86.     }
  87. }
  1. // 不超过
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 1010, INF = 0x3f3f3f3f, MOD = (int)(1e9 + 7);
  6.     static int[][] f = new int[N][N], g = new int[N][N];
  7.     static int n, m;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  14.         for (int i = 1; i <= n; i++)
  15.             Arrays.fill(f[i], -INF);
  16.         Arrays.fill(g[0], 1);
  18.         for (int i = 1; i <= n; i++) {
  19.             int v = sc.nextInt(), w = sc.nextInt();
  20.             for (int j = 0; j <= m; j++) {
  21.                 if (j >= v) {
  22.                     int max = Math.max(f[i - 1][j], f[i - 1][j - v] + w);
  23.                     int cnt = 0;
  24.                     if (max == f[i - 1][j]) cnt += g[i - 1][j];
  25.                     if (max == f[i - 1][j - v] + w) cnt += g[i - 1][j - v];
  26.                     f[i][j] = max;
  27.                     g[i][j] = cnt % MOD;
  28.                 } else {
  29.                     f[i][j] = f[i - 1][j];
  30.                     g[i][j] = g[i - 1][j];
  31.                 }
  32.             }
  33.         }
  35.         System.out.println(g[n][m]);
  36.     }
  37. }
  39. // 一维
  40. import java.util.*;
  42. public class Main {
  43.     static final int N = 1010, INF = 0x3f3f3f3f, MOD = (int)(1e9 + 7);
  44.     static int[] f = new int[N], g = new int[N];
  45.     static int n, m;
  47.     public static void main(String[] args) {
  48.         Scanner sc = new Scanner(System.in);
  49.         n = sc.nextInt();
  50.         m = sc.nextInt();
  52.         Arrays.fill(g, 1);
  54.         for (int i = 1; i <= n; i++) {
  55.             int v = sc.nextInt(), w = sc.nextInt();
  56.             for (int j = m; j >= v; j--) {
  57.                 int max = Math.max(f[j], f[j - v] + w);
  58.                 int cnt = 0;
  59.                 if (max == f[j]) cnt += g[j];
  60.                 if (max == f[j - v] + w) cnt += g[j - v];
  62.                 f[j] = max;
  63.                 g[j] = cnt % MOD;
  64.             }
  65.         }
  67.         System.out.println(g[m]);
  68.     }
  69. }

方法2：
不用g， 用dfs考虑方案的数量
从终止状态f[n][m]倒推至f[0][0]
即求dfs(n m)，在深搜的过程中计算方案数

结果会TLE，因为物品数太多了，深搜时间复杂度过高了