题解 | #购物单#

用一个笨办法做出来了，代码很长，应该是可以优化的
只把主件当成真正的i进行循环
附件部分则比较主件、主件+附件1、主件+附件2、主件+附件1+附件2的最大值
剩下的就是01背包问题
附件的id问题也费了我很大劲

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class Goods
{
public:
    Goods(int v1,int v2,int v3)
    {
        m_v=v1;
        m_p=v2;
        m_s1_v=0;
        m_s1_p=0;
        m_s2_v=0;
        m_s2_p=0;
        m_id=v3;
    }
    int m_v;
    int m_p;
    int m_s1_v;
    int m_s1_p;
    int m_s2_v;
    int m_s2_p;
    int m_id;
};
int main ()
{
    int N,m;
    cin>>N>>m;
    N=N/10;
    vector<int> temp;
    vector<vector<int>> dp;
    vector<Goods> goods;
    int v[m],p[m],q[m];
    int cnt=0;
    int temp_s;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&v[i],&p[i],&q[i]);
        if(q[i]==0)
        {
            Goods temp1(v[i]/10,p[i],i+1);
            goods.push_back(temp1);
        }
    }
    cnt=goods.size();
    for(int i=0;i<m;i++)
    {
        if(q[i]!=0)
        {
             for(int j=0;j<cnt;j++)
            {
                if(q[i]==goods[j].m_id)
                {
                    q[i]=j+1;
                }
            }
        }

    }
    for(int i=0;i<m;i++)
    {
        if(q[i]!=0)
        {
            if(goods[q[i]-1].m_s1_v==0)
            {
                goods[q[i]-1].m_s1_v=v[i]/10;
                goods[q[i]-1].m_s1_p=p[i];
            }
            else
            {
                goods[q[i]-1].m_s2_v=v[i]/10;
                goods[q[i]-1].m_s2_p=p[i];
            }
        }
    }
    for(int i=0;i<N+1;i++)
    {
        temp.push_back(0);
    }
    for(int i=0;i<cnt+1;i++)
    {
        dp.push_back(temp);
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(goods[i-1].m_v>j)
                dp[i][j]=dp[i-1][j];
            else   //四种情况，只有主件，主件+附件1，主件+附件2，主件+附件1+附件2
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-goods[i-1].m_v]+goods[i-1].m_p*goods[i-1].m_v);
                if(goods[i-1].m_s1_v+goods[i-1].m_v<=j)
                {
                    temp_s=dp[i-1][j-goods[i-1].m_v-goods[i-1].m_s1_v]+goods[i-1].m_s1_v*goods[i-1].m_s1_p+goods[i-1].m_p*goods[i-1].m_v;
                    if(temp_s>dp[i][j])
                        dp[i][j]=temp_s;
                }
                if(goods[i-1].m_s2_v+goods[i-1].m_v<=j)
                {
                    temp_s=dp[i-1][j-goods[i-1].m_v-goods[i-1].m_s2_v]+goods[i-1].m_s2_v*goods[i-1].m_s2_p+goods[i-1].m_p*goods[i-1].m_v;
                    if(temp_s>dp[i][j])
                        dp[i][j]=temp_s;
                }
                if(goods[i-1].m_s1_v+goods[i-1].m_s2_v+goods[i-1].m_v<=j)
                {
                    temp_s=dp[i-1][j-goods[i-1].m_v-goods[i-1].m_s1_v-goods[i-1].m_s2_v]+goods[i-1].m_s1_v*goods[i-1].m_s1_p+goods[i-1].m_s2_v*goods[i-1].m_s2_p+goods[i-1].m_p*goods[i-1].m_v;
                    if(temp_s>dp[i][j])
                        dp[i][j]=temp_s;
                }
            }
        }
    }
    cout<<dp[cnt][N]*10<<endl;
    return 0;
}