c语言题解 | #购物单#

主要是背包问题，记住这个公式

i是限定的最大的总价格，value是当前商品的价格，weight是当前商品的价格与重要度乘积。
注意：有附件问题要解决，买附件必须买主件买主件不一定买附件，套公式之前判断
代码如下

//背包问题，背包算法是==》f[v]=max{f[v],f[v-w[i]]+v[i]}
#include <stdio.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(void){
    //背包问题延展，有附件，最多两个，要考虑到附件
    int N,m;
    while (scanf("%d %d",&N,&m)!=EOF) {
        int value[61][3] = {0},//商品价格
        weight[61][3] = {0};//商品价格和重要度乘积
        int v=0,p=0,q=0;//v价格，p重要度，q 是否为主件以及主件的索引

        for(int i = 1;i<=m;i++){
            scanf("%d %d %d",&v,&p,&q);
            if(q){//附件
                if(!value[q][1]){//第一个附件
                    value[q][1] = v;//价格
                    weight[q][1] = v*p;//重要度
                }else{//第二个附件
                    value[q][2] = v;
                    weight[q][2] = v*p;
                }
            }else{//主件
                value[i][0] = v;
                weight[i][0] = v*p;
            }
        }

        //背包算法，价格可以整除10，减少循环
        int n=N/10,value_total = 0,weight_total = 0;
        int total_max[3200] = {0};
        for(int i=1;i<=m;i++){//循环判断每一个商品
            for(int j=n;j>=value[i][0]/10;j--){//从价格开始往下算，且单个商品的价格不能高于总价格的最大限定
                total_max[j] = max(total_max[j], total_max[j-value[i][0]/10]+weight[i][0]);//计算主件

                //计算第二个附件
                value_total = value[i][0]/10 + value[i][1]/10;
                weight_total = weight[i][0] + weight[i][1];
                if(value[i][1] && j>= value_total){
                    total_max[j] = max(total_max[j],total_max[j-value_total] + weight_total);
                }

                //计算第二个附件
                value_total += value[i][2]/10;
                weight_total += weight[i][2];
                if(value[i][2] && j>=value_total){
                    total_max[j] = max(total_max[j], total_max[j-value_total]+weight_total);
                }
            }
        }
        printf("%d\n",total_max[n]);

    }
    return 0;
}