c语言题解 | #购物单#

购物单

http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

主要是背包问题,记住这个公式
图片说明
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;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
8 7 评论
分享

全站热榜

正在热议