算法分析

01背包的转移方程f[i,j] = max(f[i - 1,j],f[i - 1,j - v] + w)
其中g[i,j] 是 f[i,j]取最大值的方案数

• 若f[i,j]是从f[i - 1,j]转移过来的，则g[i,j] = g[i - 1,j]

• 若f[i,j]是从f[i - 1,j - v] + w转移过来的，则g[i,j] = g[i - 1,j - v]

• 若f[i,j]均能从f[i - 1,j]和f[i - 1,j - v] + w转移过来的，则g[i,j] = g[i - 1,j] + g[i - 1,j - v]

将所有的最大值所对应的方案数累加在一起，即为方案数总和

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

参考文献

算法提高课

Java 代码

import java.util.Scanner;
public class Main {
    static int N = 1010;
    static int mod = 1000000007;
    static int[] f = new int[N];
    static int[] g = new int[N];
    public static void main(String[] args){
       Scanner scan = new Scanner(System.in);
       int n = scan.nextInt();
       int m = scan.nextInt();
       f[0] = 0;
       g[0] = 1;
       for(int i = 1;i <= n;i++)
       {
           int v = scan.nextInt();
           int w = scan.nextInt();
           for(int j = m;j >= v;j --)
           {
               int maxv = Math.max(f[j], f[j - v] + w);
               int cnt = 0;
               if(maxv == f[j]) cnt = (cnt + g[j]) % mod ;
               if(maxv == f[j - v] + w) cnt = (cnt + g[j - v]) % mod;
               g[j] = cnt;
               f[j] = maxv;
           }
       }
       //f[m]是最大值
       int cnt = 0;
       for(int i = 0;i <= m;i++)
           if(f[i] == f[m])
               cnt = (cnt + g[i]) % mod;
        System.out.println(cnt);
    }
}