题目描述

有 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

Tips: 选不了某一组的其中一物品，该状态下的最优解可能包括该组的其它物品，所以选不了其中一物品，
也应该考虑该组的其它物品;
所以转移方程就有略微的变化：
if (v >= ali[i][m].v)dp[i][v] = std::max(dp[i - 1][v - ali[i][m].v] + ali[i][m].w, dp[i][v]);
else dp[i][v] = std::max(dp[i - 1][v],dp[i][v]);

C++ 代码

#include<vector>
#include<iostream>
#include<algorithm>

struct kk
{
    int v, w;
};
int N, V;
std::vector<struct kk>ali[107];
int dp[107][107] = { {} };

int main(void)
{
    scanf("%d %d", &N, &V);
    int num, a, b;
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &num);
        while (num--)
        {
            scanf("%d %d", &a, &b);
            ali[i].push_back({ a,b });
        }
    }
    for (int i = 1; i <= N; i++)
    {
        for (int v = 0; v <= V; v++)
        {
            dp[i][v] = dp[i - 1][v];//假设当前选取到i组体积为v时，最优解为不选取该组任何物品
            for (int m = 0; m < ali[i].size(); m++)//遍历所有物品
                if (v >= ali[i][m].v)
                    dp[i][v] = std::max(dp[i - 1][v - ali[i][m].v] + ali[i][m].w, dp[i][v]);
            //如果此时体积可以容纳下该组的这一物品，则有原来不包括这一组的这一物品的最优解，可是
            //可能会有这一组的别的物品，而题意要求每组只能选取一个，所以把上一组的最优解加上选这个
            //的结果，与不选这个但是可能会选该组其它物品的解值进行对比，才可以得出最优解
                else dp[i][v] = std::max(dp[i - 1][v], dp[i][v]);
            //如上所说选不了这个不代表该体积状态下的其他物品，所以要与不选这个却选了该组其它物品的最优解
            //与体积为v状态下本组不选任何物品的解进行对比，选出该状态的最优解
        }
    }
    printf("%d", dp[N][V]);
    return 0;
}