题解 | #购物单#

c++有依赖的动态规划

将主件相同的情况分为一组：

** 1.主件...2主件+附件1...3主件+附件2 ...4主件+附件1+附件2 ** 无非上述这四种情况

从而将有依赖的背包问题转成分组背包问题，每一组只能选一种情况

#include  <bits/stdc++.h>
using namespace std;
const int N =62,M=33000;
int v[N],p[N],q[N],dp[M],f[N*4][N*4],w[N*4][N*4];
//记录该主的下标，以及增量，以及是否是第一个附件
int s[N],k[N],a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>v[i]>>p[i]>>q[i];
    int cnt=0;
    //将同一主键的分为一组，无非四种情况1.主件  2主件+附件1  3主件+附件2   4主件+附件1+附件2
    for(int i=1;i<=m;i++){
        if(q[i]==0){//为主件
            if(s[i]==0){//下标没添加该组
                ++cnt;
                s[i]=cnt;
                w[s[i]][++k[i]]=v[i];
                f[s[i]][k[i]]=v[i]*p[i];
                
            }else{//已经添加该组
                 w[s[i]][++k[i]]=v[i];
                f[s[i]][k[i]]=v[i]*p[i];
            }
        } else if(q[i]&&(a[q[i]]==0)){//第一个附件
              if(s[q[i]]==0){//且下标没添加该组
                ++cnt;
                s[q[i]]=cnt;
                w[s[q[i]]][++k[q[i]]]=v[i]+v[q[i]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+v[q[i]]*p[q[i]];
                a[q[i]]=k[q[i]];
            }else{//已经添加该组
                 w[s[q[i]]][++k[q[i]]]=v[i]+v[q[i]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+v[q[i]]*p[q[i]];
                a[q[i]]=k[q[i]];
            }
        }else{//第二个附件
              w[s[q[i]]][++k[q[i]]]=v[i]+v[q[i]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+v[q[i]]*p[q[i]];
              w[s[q[i]]][++k[q[i]]]=v[i]+w[s[q[i]]][a[q[i]]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+f[s[q[i]]][a[q[i]]];
        }
        
    }
    for(int i=1;i<=cnt;i++){
        for(int j=n;j>=0;j--){
          // dp[i][j]=dp[i-1][j];
            for(int y=1;y<=4;y++){
                if(j>=w[i][y]){
              
                    dp[j]=max(dp[j],dp[j-w[i][y]]+f[i][y]);
                  
                }
                
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

#非优化空间版本#

using namespace std;
const int N =62,M=33000;
int v[N],p[N],q[N],dp[4*N][M],f[N*4][N*4],w[N*4][N*4];
//记录该主的下标，以及增量，以及是否是第一个附件
int s[N],k[N],a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>v[i]>>p[i]>>q[i];
    int cnt=0;
    //将同一主键的分为一组，无非四种情况1.主件  2主件+附件1  3主件+附件2   4主件+附件1+附件2
    for(int i=1;i<=m;i++){
        if(q[i]==0){//为主件
            if(s[i]==0){//下标没添加该组
                ++cnt;
                s[i]=cnt;
                w[s[i]][++k[i]]=v[i];
                f[s[i]][k[i]]=v[i]*p[i];
                 
            }else{//已经添加该组
                 w[s[i]][++k[i]]=v[i];
                f[s[i]][k[i]]=v[i]*p[i];
            }
        } else if(q[i]&&(a[q[i]]==0)){//第一个附件
              if(s[q[i]]==0){//且下标没添加该组
                ++cnt;
                s[q[i]]=cnt;
                w[s[q[i]]][++k[q[i]]]=v[i]+v[q[i]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+v[q[i]]*p[q[i]];
                a[q[i]]=k[q[i]];
            }else{//已经添加该组
                 w[s[q[i]]][++k[q[i]]]=v[i]+v[q[i]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+v[q[i]]*p[q[i]];
                a[q[i]]=k[q[i]];
            }
        }else{//第二个附件
              w[s[q[i]]][++k[q[i]]]=v[i]+v[q[i]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+v[q[i]]*p[q[i]];
              w[s[q[i]]][++k[q[i]]]=v[i]+w[s[q[i]]][a[q[i]]];
                f[s[q[i]]][k[q[i]]]=v[i]*p[i]+f[s[q[i]]][a[q[i]]];
        }
         
    }
    for(int i=1;i<=cnt;i++){
        for(int j=n;j>=0;j--){
          dp[i][j]=dp[i-1][j];
            for(int y=1;y<=4;y++){
                if(j>=w[i][y]){
               
                    dp[i][j]=max(dp[i][j],dp[i-1][j-w[i][y]]+f[i][y]);
                   
                }
                 
            }
        }
    }
    cout<<dp[cnt][n]<<endl;
    return 0;
}