题目分析

首先这道题目是背包九讲里面第7讲中的有依赖的背包（不过那篇我没怎么看懂），本题中我们可以把附件和主件看成一组，总共有4种情况。

1.选主件 不选附件

2.选主件 选附件1

3.选主件 选附件2

4.选主件 选附件1 和 选附件2

这四种情况，我们可以可以做一次01背包，选出主件这一组中这四种情况中的最大价值即可。

还有一个优化是 因为钱是10的倍数 可以除以10  减少空间占用

#include 
      
       #include 
       
        using namespace std;int n,m,V;int v[62],w[62],v1[62],w1[62],v2[62],w2[62];int dp[5005];int ans;int main(){    scanf("%d%d",&V,&m);    V/=10;    for(int i=1;i<=m;i++){        int x,y,z;        scanf("%d%d%d",&x,&y,&z);        x/=10;        if(z){            if(!v1[z]){                v1[z]=x;                w1[z]=x*y;            }            else{                v2[z]=x;                w2[z]=x*y;            }        }        else{            v[i]=x;            w[i]=y*x;            n=i;        }    }    for(int i=1;i<=n;i++)        for(int j=V;j>=v[i];j--){            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);            if(j-v[i]-v1[i]>=0) dp[j] = max(dp[j],dp[j-v[i]-v1[i]]+w[i]+w1[i]);            if(j-v[i]-v1[i]-v2[i]>=0) dp[j] = max(dp[j],dp[j-v[i]-v1[i]-v2[i]]+w[i]+w1[i]+w2[i]);            if(j-v[i]-v2[i]>=0) dp[j] = max(dp[j],dp[j-v[i]-v2[i]]+w[i]+w2[i]);        }    printf("%d",dp[V]*10);    return 0;}