题解 | #购物单#

//转化为背包问题
#include <stdio.h>
int main(){
    int N,m;      //总钱数、希望购买物品的个数
    int v,p,q;    //v物品价格、p物品重要程度、q=0为主件 q>0为某主件的附件，q值就是主件的编号
    /*1000 5
      800 2 0
      400 5 1
      300 5 1
      400 3 0
      500 2 0
      五个物品，默认每个买一件。要求买附件必须买主件，买主件不必要买附件
      第一个物品有四种组合方式：800、800+400、800+300、800+400+300
      后两个物品没有附件，不考虑主附件限制。*/
    int gv[61][4];     //定义 vq 数组来反应物品（主附组合）价格
    int gw[61][4];     //定义 vp 数组来表示物品（主附组合）价值（价格 * 重要度）
    int dp[3200] = {0}; //表示放入背包内的现有物品的总价值
    //对附件进行主件二维数组的排列存储
    scanf("%d%d",&N,&m);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d",&v,&p,&q);
        if(q == 0){    //存为主件
            gv[i][0] = v / 10;
            gw[i][0] = v * p / 10;
        }
        else{   //大于 0 的存为对应附件（要求：输入时附件就跟在对应主件后面）
            if(gv[q][1]){     //如果有第一个附件，就存为第二个附件
                gv[q][2] = v / 10;
                gw[q][2] = v * p / 10;
            }else{           //如果没有第一附件就存为第一附件
                gv[q][1] = v / 10;
                gw[q][1] = v * p / 10;
            }
        }
    }
    //主附件组合（不在读取时组合是因为数据可能是附件在前主件在后）
    for(int i = 1; i <= m; i++){
        //主件 + 第一附件
        gv[i][1] += gv[i][0];
        gw[i][1] += gw[i][0];
        //主件 + 第二附件
        gv[i][2] += gv[i][0];
        gw[i][2] += gw[i][0];
        //主件 + 第一附件 + 第二附件
        gv[i][3] = gv[i][1] + gv[i][2] - gv[i][0] ;
        gw[i][3] = gw[i][1] + gw[i][2] - gw[i][0];
    }
    //状态方程：f(m,N) = dp[i][j] = max(dp[i][j],dp[i-1][j-gv[i][k]] + gw[i][k])
    for(int i = 1; i <= m; i++){
        for(int j = N/10; j > 0; j--){
            //dp[i][j] = dp[i-1][j];     //什么都不买，即不买该主件（只买附件不合题意排除）
            for(int k = 0; k <= 3; k++){
                //（0）主件
                //（1）主件 + 附件1
                //（2）主件 + 附件2
                //（3）主件 + 附件1 + 附件2
                int tmp = dp[j - gv[i][k]] + gw[i][k];
                if(gv[i][k] <= j && dp[j] < tmp){
                    dp[j] = tmp;
                }
            }
        }
    }
    
    printf("%d",dp[N/10] * 10);
    return 0;
}

无

无