华为OD机考(HJ16 购物单)

作者：酷酷是懒虫 | 2024-06-27 08:47:11

踩

华为OD机考(HJ16 购物单)

前言

应广大同学要求，开始以OD机考题作为练习题，看看算法和数据结构掌握情况。有需要练习的可以关注下。此题难度略大，需要对背包问题较为熟悉，同时题干信息量较大，都为解题造成了一定难度。

在开始此题前请提前查看Java数据结构与算法(0/1背包问题)-CSDN博客，否则理解有些困难。

描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。

王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/761915