思路:
import java.io.*;
import java.util.*;
/**
* f[i]表示体积恰好是i时的最大价值, g[i]记录最大体积时的方案数
*/
public class Main {
public static int N = 1010, mod = (int) 1e9 + 7;
public static int[] f = new int[N], g = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]), c = Integer.parseInt(s1[1]);
Arrays.fill(g, 1); // 背包里什么也不装也是一种方案
for (int i = 0; i < n; i++) {
s1 = br.readLine().split(" ");
int v = Integer.parseInt(s1[0]), w = Integer.parseInt(s1[1]);
for (int j = c; j >= v; j--) {
int newv = f[j - v] + w;
if (newv > f[j]) { // 选i更大,直接更新g。不选i更大那么就不用更新。
f[j] = newv;
g[j] = g[j - v];
} else if (newv == f[j]) // 两者相等累加g
g[j] = (g[j] + g[j - v]) % mod;
}
}
bw.write(g[c] + "\n");
bw.flush();
}
}