华为OJ——购物单

2024-05-15 22:08
文章标签 华为 oj 购物单

本文主要是介绍华为OJ——购物单,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

购物单

题目描述

王强今天很开心,公司发给N元的年终奖。王强决定把年终奖用于购物,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

主件

附件

电脑

打印机,扫描仪

书柜

图书

书桌

台灯,文具

工作椅

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多,为了不超出预算,他把每件物品规定了一个重要度,分为 5 等:用整数 1 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是 10 元的整数倍)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

    设第 j 件物品的价格为 v[j] ,重要度为 w[j] ,共选中了 k 件物品,编号依次为 j 1  j 2 …… j k ,则所求的总和为:

v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。(其中 * 为乘号)

    请你帮助王强设计一个满足要求的购物单。

输入描述:

输入的第 1 行,为两个正整数,用一个空格隔开:N m

(其中 N  <32000 )表示总钱数, m  <60 )为希望购买物品的个数。)

从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个非负整数 v p q

(其中 v 表示该物品的价格( v<10000 ), p 表示该物品的重要度( 1 ), q 表示该物品是主件还是附件。如果 q=0 ,表示该物品为主件,如果 q>0 ,表示该物品为附件, q 是所属主件的编号)

输出描述:

 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值( <200000 )。

 

输入例子:

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

 

输出例子:

2200

#include <iostream>
using namespace std;
typedef struct
{int value;int weight;int judge;
} list;
int main()
{//总的钱数和物品数量int money,total;cin>>money>>total;//输入商品信息list goods[61];int dynamicList[61][3200];//初始化dynamicListmemset(dynamicList,0,sizeof(dynamicList));//输入数据for(int i=1; i<=total; i++){cin>>goods[i].value>>goods[i].weight>>goods[i].judge;}//动态规划:构造一张表for(int j=1; j<=money; j++){for(int i=1; i<=total; i++){//该商品为主件if(!goods[i].judge){if(goods[i].value<=j)dynamicList[i][j]=dynamicList[i-1][j]>(dynamicList[i-1][j-goods[i].value]+goods[i].value*goods[i].weight)?dynamicList[i-1][j]:(dynamicList[i-1][j-goods[i].value]+goods[i].value*goods[i].weight);}//该商品为附件if(goods[i].judge){if(goods[i].value+goods[goods[i].judge].value<=j)dynamicList[i][j]=dynamicList[i-1][j]>(dynamicList[i-1][j-goods[i].value]+goods[i].value*goods[i].weight)?dynamicList[i-1][j]:(dynamicList[i-1][j-goods[i].value]+goods[i].value*goods[i].weight);}}}cout<<dynamicList[total][money]<<endl;return 0;
}

这篇关于华为OJ——购物单的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/993046

相关文章

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群 华为云最近正在举办828 B2B企业节,Flexus X实例的促销力度非常大,特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Nginx等服务的需求,一定不要错过这个机会。赶紧去看看吧! 什么是华为云Flexus X实例 华为云Flexus X实例云服务是新一代开箱即用、体

华为OD机试真题-学生方阵-2024年OD统一考试(E卷)

题目描述 学校组织活动,将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上,方向可以是水平的,垂直的,成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数, 接下来的 n行为矩阵元素,元素间用""分隔。 输出描述 输出一个整数,表示矩阵中最长的位

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案:B 解析: 暂无解析 2..两台路由器直连,并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项? A、使用组播地址 224.0.0.6 B

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器(MQTT协议)

MQTT协议概述 MQTT(Message Queuing Telemetry Transport)是一种轻量级的消息传输协议,它被设计用来提供一对多的消息分发和应用之间的通讯,尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构,客户端可以订阅任意数量的主题,并可以发布消息到这些主题。服务器(通常称为MQTT Broker)则负责接受来自客户端的连接请求,并转发消

华为23年笔试题

消息传输 题目描述 在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中,分布着一些信号塔,用于区域间通信。 每个单元格可以有以下三种状态:  值 0 代表空地,无法传递信号;  值 1 代表信号塔 A,在收到消息后,信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔; 值 2 代表信号塔 B,在收到消息后,信号塔 B 可以在 2ms

实现的动态规划问题华为笔试题C++实现

秋招刷力扣题,我觉得我对动态规划不是熟练,在此处做总结 动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。我觉得最大的问题就是对问题的分解,分解后的问题与分解前的问题具有相同的决策机制,将决策机制进行抽象,最终可以得到对应的解; 动态规划中开始介绍的爬楼梯等问题,答

828华为云征文|基于华为云Flexus云服务器X实例部搭建Halo博客平台

华为云征文|基于华为云Flexus云服务器X实例部搭建Halo博客平台 前言一、Flexus云服务器X实例介绍1.1 Flexus云服务器X实例简介1.2 Flexus云服务器X实例特点1.3 Flexus云服务器X实例使用场景 二、Halo介绍2.1 Halo 简介2.2 Halo 特点 三、本次实践介绍3.1 本次实践简介3.2 本次环境规划 四、购买华为云Flexus云服务器X实例4.

三方登录 - 华为登录

1.1. 开发准备 当应用需要使用以下开放能力的一种或多种时,为正常调试运行应用,需要预先添加公钥指纹 Account Kit(华为帐号服务)Call Kit(通话服务)Game Service Kit(游戏服务)Health Service Kit(运动健康服务)IAP Kit(应用内支付服务)Live View Kit(实况窗服务,当需要使用Push Kit时必须执行此步骤)Map Kit

828华为云征文|基于Flexus云服务器X实例的应用场景-拥有一款自己的ssl监控工具

先看这里 写在前面效果图华为云Flexus云服务器X实例介绍特点可选配置购买 连接服务器Uptime-kuma简介开源信息部署准备工作:docker部署命令访问uptime-kuma 基本配置总结 写在前面 作为一个个人开发者,相信你手里肯定也有不少自己的服务,有的服务呢也是https的。 以前ssl各厂都是可以免费申请一年的,我们更换的频率还好,比较小;但是最近,各厂都

828华为云征文|基于华为云Flexus X实例搭建Nginx集群负载均衡

目录 前言 一、Flexus云服务器X介绍 1.1 Flexus云服务器X实例简介 1.2 Flexus X实例购买 1.3 登录服务器 三、Springboot集群服务 3.1 部署9901节点服务 3.2 部署9902节点服务 四、Nginx负载均衡配置 五、集群负载调用测试 5.1 负载调用9901端口 5.2 负载调用9901端口 总结 前言 华为云Flexus X实例凭借其