AcWing 11. 背包问题求方案数-Java实现
原题链接
中等
作者:
FUZZ
,
2019-10-31 16:37:51
,
所有人可见
,
阅读 1184
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] arg){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int C = sc.nextInt();
int[] dp1 = new int[C + 1]; // dp1[i][j] 表示面对前i个物品,当前容量为j时的最大价值
int[] dp2 = new int[C + 1]; // dp2[i][j] 表示面对前i个物品,当前容量为j最大价值的方案数
Arrays.fill(dp2, 1); // 就算一个也不拿,也是一种方案
for(int i = 0; i < N; i++){
int vi = sc.nextInt(); // 体积
int wi = sc.nextInt(); // 价值
for(int j = C; j >= vi; j--){
int get = dp1[j - vi] + wi;
if(get == dp1[j]){
dp2[j] += dp2[j - vi];
}else if(dp1[j] < get){
dp1[j] = get;
dp2[j] = dp2[j - vi];
}
dp2[j] %= 1000000007;
}
}
System.out.println(dp2[C]);
}
}