题解 | #购物单#

对于我这种新手来说，如何把数据进行抽象就是一个难题，当然这也是考察编程能力的一部分，考察过程抽象与数据抽象，在本题中，存在N件商品，可以分为主体和附件，首先需要画出这样一个表，帮助理解数据该怎样读入。

在数据保存下来后，分析该问题发现是我们常见的背包问题：在总钱数有限的条件下，获取最大价值。
但是该问题中，附件的存在影响我们动态方程的求解.
在背包问题中，设dp[i][j]表示在钱数不超过j的条件下，对于前i件产品的选择所能获取的最大价值。
动态方程可以表示为
如果j>price[i] dp[i][j]=max(dp[i][j-price[i]]+value[i],dp[i-1][j])
否则 dp[i][j]=dp[i-1][j])
那么如何处理附件,我们知道，这里的编号都是主件，所以在每一主件之后可以增加对附件的判断
dp[i][j]=max(主件，主件+附件1，主件+附件2，主件+附件3，不买主件)
这里偶尔会产生困扰思想，肯定买的越多，价值越多，那么还用判断吗？当然用，因为买的越多，剩余的钱数就越少，能买其他编号的数量也越少，我们就是要求出，在任意钱数下，能达到的最大价值。
代码如下：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int M,N;
    cin>>M>>N;
    M/=10;
    vector<vector<int>> price(N+1,vector<int>(3,0));
    vector<vector<int>> value(N+1,vector<int>(3,0));
    for(int i=1;i<=N;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c==0){
            price[i][0]=a/10;
            value[i][0]=b;
        }
        else{
            if(price[c][1]!=0){
                price[c][2]=a/10;
                value[c][2]=b;
            }
            else{
                price[c][1]=a/10;
                value[c][1]=b;
            }
        }
    }
    vector<vector<int>> dp(N+1,vector<int>(M+1,0));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            int a=price[i][0],b=value[i][0];
            int c=price[i][1],d=value[i][1];
            int e=price[i][2],f=value[i][2];
            dp[i][j]=j>=a?max(dp[i-1][j-a]+a*b,dp[i-1][j]):dp[i-1][j];
            dp[i][j]=j>=a+c?max(dp[i-1][j-a-c]+a*b+c*d,dp[i][j]):dp[i][j];
            dp[i][j]=j>=a+e?max(dp[i-1][j-a-e]+a*b+e*f,dp[i][j]):dp[i][j];
            dp[i][j]=j>=a+c+e?max(dp[i-1][j-a-e-c]+a*b+c*d+e*f,dp[i][j]):dp[i][j];
        }
    }
    cout<<dp[N][M]*10<<endl;
    return 0;
}