C 语言 购物单问题

购物单

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

注意此代码默认,一件物品只能买一次
而输入顺序可以随机

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

int main(void){
    int N,m; // N:钱,M总物品数
    scanf("%d %d",&N,&m);
    int x,y,z;
    int value[m][4];// 价钱与重要度乘积
    int cost[m][4];// 价钱,0:主;1、2:附
    memset(value, 0, m * 4 * sizeof(int));
    memset(cost, 0, m * 4 * sizeof(int));

    for(int i=0;i<m;i++){
        scanf("%d %d %d", &x, &y, &z);
        // 分主附件,转化01背包问题
        // 计算四种情况的value和cost
        if(z==0){
            value[i][0]=x*y;
            cost[i][0]=x;
        }
        else if(cost[z-1][1]==0){
            // 第z件为其主件,对应下标z-1
            cost[z-1][1]=x;
            value[z-1][1]+=x*y;
        }
        else{
            cost[z-1][2]=x;
            value[z-1][2]=x*y;
            cost[z-1][3] = cost[z-1][1]+cost[z-1][2];
            value[z-1][3] = value[z-1][1]+value[z-1][2];
        }
    }
    for(int i=0;i<m;i++){
        for(int k=1; k<4;k++){
            cost[i][k] += cost[i][0];
            value[i][k] += value[i][0];
        }
    }

//     for(int i=0; i<m; i++){
//         for(int k=0;k<4;k++)
//             printf("%d %d    ", cost[i][k], value[i][k]);
//         printf("\n");
//     }

    int dp[m+1][N+1];
    int max_v=0;
    memset(dp, 0, (m+1)*(N+1)*sizeof(int));
    // 可以考虑优化,0行略过
    for(int i=1; i<=m; i++){
        for(int j=10;j<=N;j+=10){
            max_v = dp[i-1][j];
            for(int k=0;k<4;k++){
                if(k>0 && cost[i-1][k]==cost[i-1][0])
                    break;
                if(j-cost[i-1][k]>=0)
                    max_v = max(max_v,dp[i-1][j-cost[i-1][k]]+value[i-1][k]);
            }
            dp[i][j] = max_v;
        }
    }
    printf("%d", dp[m][N]);
    return 0;
}
全部评论

相关推荐

05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
存一千万就可以进大厂实习
石圪节公社发型师:有存一千万的实力还实习个嘚,直接躺平
点赞 评论 收藏
分享
评论
12
10
分享

创作者周榜

更多
牛客网
牛客企业服务