分组背包

⬅ 返回

1、闫氏DP分析法

2、例题

3、代码

3.1、二维dp

#include <iostream>
using namespace std; 
const int N = 1e4;
int dp[N][N];//dp[i][j] 表示 前i组 在 容量为j 的条件下的最大价值
int v[N][N],w[N][N];
int ct[N];//记录每一组有多少个物品
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int s;
        cin>>s;
        ct[i]=s;
        for(int j=1;j<=s;j++)
        {
            int a,b;
            cin>>a>>b;
            v[i][j]=a;
            w[i][j]=b;
        }
    }
    for(int i=1;i<=n;i++)//n组
    {
       for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];//不选
            for(int k=1;k<=ct[i];k++)//遍历该组的物品
            {
                if(v[i][k]<=j)
                    dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][k]]+w[i][k]);
            }
            
        }
        
    }
    cout<<dp[n][m]<<endl;
    
}

3.2、一维优化

#include <iostream>
using namespace std; 
const int N = 1e4;
int dp[N];//dp[i][j] 表示容量为j 的条件下的最大价值
int v[N][N],w[N][N];
int ct[N];//记录每一组有多少个物品
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int s;
        cin>>s;
        ct[i]=s;
        for(int j=1;j<=s;j++)
        {
            int a,b;
            cin>>a>>b;
            v[i][j]=a;
            w[i][j]=b;
        }
    }
    for(int i=1;i<=n;i++)//n组
    {
       for(int j=m;j>=0;j--)//容量从大到小 因为要用上一轮的数据 
       //若用的是这一轮的数据来回更新那就是完全背包
        {
            for(int k=1;k<=ct[i];k++)//遍历该组的物品
            {
                if(v[i][k]<=j)
                    dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
            }
            
        }
        
    }
    cout<<dp[m]<<endl;
    
}