有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

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

输出最大价值。

输入格式

第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量.

接下来有 N 组数据:

  • 每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
  • 每组数据接下来有 Si 行,每行有两个整数 vij, wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0 < N, V ≤ 100 0 < Si ≤ 100 0 < vij, wij ≤ 100

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例

8

代码实现

#include <iostream>
using namespace std;
const int N = 1e4;

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

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status