题目描述

01背包是判定要不要用这个物品，这道题也是判定要不要用这个物品,只是同一个组只能选一个，于是怎么才能体现出同一组只能选一个？

跟遍历顺序有关，如一个大小为4的DP数组XXXX，第 i 组的时候，对一个体积上限(如DP[3]），对它连续判断、更新s次，其中s是该组的物品个数，更新完了之后，移动到DP的另一个体积上限（也就是j在变化，如到DP[2]），到 i+1 组之前不更新DP[3]这个体积上限了，重复这个过程，这样子能体现只用了一个该组的物品。

即两个for循环，先遍历体积j，再遍历物品种类s

如果反过来，先遍历物品种类s，再遍历体积j，就是普通的01背包，没有考虑分组的情况

算法1

C++ 代码

#include <iostream>
using namespace std;
const int si =101;
int f[si],w[si],v[si];
int main() {
    int N, V;
    cin >> N >> V;
    for (int i=0; i<N; i++){
        int s;
        cin >> s;
        for (int j=0;j<s;j++) cin >> v[j]>>w[j];
        for (int j=V;j>=1;j--) {
            for (int k=0;k<s;k++){
                if (j>=v[k]) f[j] = max(f[j], f[j-v[k]]+w[k]);
            }
        }
    }
    cout <<f[V]<<endl;
}