动态规划——分组背包

问题描述

分组背包：有N组物品，背包体积为V；选法：每一组物品里面只能选择一个；结果：总体积不超过V的最大价值

问题解决

问题链接：分组背包 还是要搞定状态方程：注意下标表示的含义 f[i][j]表示：从0到i组物品中选择体积不超过j的，且总价值最大。 下面思考：第i组可以怎么选，选择第i组里面的第0个物品，第1个物品，第2个物品，第3……的最大值 f[i][j]=max(f[i-1][j],f[i-1][j-vi1] wi1,f[i-1][j-vi2] wi2............)

代码语言：javascript复制

cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int N,V;
    cin>>N>>V;
    vector<vector<int>> v(N 1),w(N 1);
    for(int i=1;i<=N;i  )
    {
        int a,b,c;
        cin>>a;
        v[i].push_back(0);
        w[i].push_back(0);
        while(a--)
        {
            cin>>b>>c;
            v[i].push_back(b);
            w[i].push_back(c);
        }
    }
    vector<vector<int>> f(N 1,vector<int>(V 1));
    for(int i=1;i<=N;  i)
    {
        for(int j=1;j<=V;j  )
        {
            for(int s=0;s<v[i].size();s  )
            if(v[i][s]<=j)
            f[i][j]=max(f[i][j],f[i-1][j-v[i][s]] w[i][s]);
        }
    }
    cout<<f[N][V]<<endl;
    return 0;
}

include int push vector 动态规划

0 人点赞