购物单：C语言解法

通常 背包问题 相关的题，都是在考察我们的建模的能力，也就是将问题转换为 背包问题 的能力。
很容易看出本题的成本可以看成是物品的价格
价值可以看成物品的（价格*权重）
唯一混淆的可能是附件，但由于附件是和主件绑定的，那么附件单独出现可以不用考虑，主件出现的时候则需考虑与附件不同组合时的成本和价值，把每种组合看成是每一个整体去动态规划

#include<stdio.h>
#include<math.h>
int main(){
    int money = 0, num = 0;
    scanf("%d %d\n",&money, &num);
    int v, p, q;
    //创建两个二维数组，可以把（主件,主件+附件1,主件+附件2,主件+附件1+附件2）每样看成一个完整物品做动态规划
    int weight[num][4];//每个物品的价值（价格*权重）
    int cost[num][4];//每个物品的成本（价格）
    memset(weight, 0, sizeof(weight));
    memset(cost, 0, sizeof(cost));
    //初始化数组，添加每个物品的价值和成本,先不要加上主件，如果附件先给出那么因为主件的值还为0，会初始化错误
    for(int i=0; i<num; i++){
        scanf("%d %d %d\n",&v, &p, &q);
        if(q == 0){//如果这个物品不是附件，直接放到数组里
            weight[i][0] = v*p;
            cost[i][0] = v;
        }else if(cost[q-1][1] == 0){//如果是并且是物品q的第一个附件，(第一次提交的错误：加上主件的成本还有价值放到组组里)
            weight[q-1][1] = v*p;
            cost[q-1][1] = v;
        }else{//如果是并且是物品q的第二个附件，同上
            weight[q-1][2] = v*p;
            cost[q-1][2] = v;
            weight[q-1][3] = v*p + weight[q-1][1];
            cost[q-1][3] = v + cost[q-1][1];
        }
    }
    //所以需要重新加主件一次（初始化的时候就不用加了）
    for(int j=0; j<num; j++){
        if(cost[j][0] != 0 || cost[j][1] == 0){//附件或没有附件的主件就不用加了
            for(int k=1; k<4; k++){
                 weight[j][k] += weight[j][0];
                 cost[j][k] += cost[j][0];
            }
        }
    }
    int dp[money+1];//用一维数组做动态规划
    memset(dp, 0, sizeof(dp));//所有值初始化为0
    for(int x=0; x<num; x++){ 
      if(cost[x][0] == 0) continue;//如果是附件就不用单独买（动态规划剪枝）
        for(int y=money; y>0; y-=10){
            for(int z=0; z<4; z++){
                if(y >= cost[x][z]){//买完钱有富余或正好可以买下时
                    dp[y] = fmax(dp[y],weight[x][z]+dp[y-cost[x][z]]);//把当前的最大值放到数组里
                }
            }
        }
    }
    printf("%d\n",dp[money]);
}

代码还可以进行优化

初始化的dp数组很大，但实际上却只用了money/10个空间，可以缩小dp数组
没有附件的主件还会进入z<4的循环，可以进行剪枝

题解 | #购物单#

购物单：C语言解法