动态规划

(类似01背包) $O(N*V)$

C++ 代码

#include<iostream>
using namespace std;

const int MOD = 1000000000 + 7;
int N, V;
int dp[1000 + 1];
int nums[1000 + 1];

int main(){
    cin >> N >> V;
    for(int j = 0; j <= V; j++){
        dp[j] = 0;
        nums[j] = 1;
    }
    for(int i = 0; i < N; i++){
        int v, w;
        cin >> v >> w;
        // 类似01背包，从后往前计算。
        for(int j = V; j >= v; j--){
            if(dp[j] < dp[j - v] + w){
                dp[j] = dp[j - v] + w;
                nums[j] = nums[j - v];
            }else if(dp[j] == dp[j - v] + w){
                nums[j] += nums[j - v];
                nums[j] %= MOD;
            }
        }
    }
    cout << nums[V];

    return 0;
}