有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出最优选法的方案数。注意答案可能很大,请输出答案模 10^9+7 的结果。

输入格式

第一行两个整数,N 和 V,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数,表示方案数模 10^9+7 的结果。

数据范围

0 < N, V ≤ 1000 0 < vi, wi ≤ 1000

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例

2

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10, MOD = 1e9 + 7;

int n, V, v, w, g[N], dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    g[0] = 1;
    while(n--) {
        cin >> v >> w;
        for (int i = V; i >= v; --i) {
            int cnt = 0, mx = max(dp[i], dp[i - v] + w);
            if (mx == dp[i]) cnt += g[i];
            if (mx == dp[i - v] + w) cnt += g[i - v];
            g[i] = cnt
            dp[i] = mx;
        }
    }
    int cnt = 0, mx = *max_element(dp, dp + V + 1);
    for (int i = 0; i <= V; ++i) if (mx == dp[i]) cnt = (cnt + g[i])
    cout << cnt;
    return 0;
} 
分类: AlgorithmDP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status