背包问题之求方案数

package com.zhang.reflection.面试.算法模版.背包问题模版;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
 *
 * 第 i 件物品的体积是 vi，价值是 wi。
 *
 * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
 *
 * 输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。
 *
 * 输入格式
 * 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
 * 4 5
 * 1 2
 * 2 4
 * 3 4
 * 4 6
 *
 * 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
 * 2
 * 输出格式
 * 输出一个整数，表示 方案数 模 109+7 的结果。
 */

public class 求方案数 {
    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]);
    }
}