首页 > 试题广场 >

购物单

[编程题]购物单
  • 热度指数：452546 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第i件物品的价格为，重要度为，共选中了k件物品，编号依次为j_1,j_2,...,j_k，则满意度为：。（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。




输入描述:
输入的第 1 行，为两个正整数N，m，用一个空格隔开。其中 N 表示总钱数， m 为可购买的物品的个数。

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

其中 v 表示该物品的价格，p 表示该物品的重要度，q 表示该物品是主件还是附件。

如果 q=0，表示该物品为主件，如果q>0，表示该物品为附件， q 是所属主件的编号。



数据范围：N<32000，m<60，v<10000，1<=p<=5。


输出描述:
 输出一个正整数，为张强可以获得的最大的满意度。
示例1

输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出

2200
示例2

输入

50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

输出

130

说明

由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
算法知识视频讲解
开通博客
头像 牛客443689898号
发表于 2020-04-23 23:53:29
购物车 其实这题就是0-1背包问题 首先来看一下经典背包问题，稍作修改就可以得出这题的解答 0-1背包问题 问题描述：有一个背包可以装物品的总重量为W，现有N个物品，每个物品中w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？ 定义状态转移数组dp[i][j]，表示前i个物品，背包重量为j 展开全文
去ta的博客 赞 (826) 回复(60) 收起
头像 华科不平凡
发表于 2020-08-27 17:20:37
出题者觉得0/1背包太套路了，因此给我们使了点小绊子，但是问题不大。 设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多 展开全文
去ta的博客 赞 (324) 回复(37) 收起
头像 Naruto23
发表于 2020-04-23 15:18:26
Java版本 具体思路就是构造物品类，然后对主件判断是否有附件，若有附件则依次添加，根据主件、附件1、附件2的组合有四种情况 只有主件 主件+附件1 主件+附件2 主件+附件1+附件2根据以上情况转化问题为经典的 01背包问题 ，接着就是套公式动态规划即可 该题解参考了博客园舞动的心的算法笔记， 展开全文
去ta的博客 赞 (154) 回复(49) 收起
头像 限时烟花
发表于 2021-10-23 22:24:49
HJ16 购物单 题解 by 限时烟花 1. 抽丝剥茧 看到题目的第一想法就是很像背包问题，如果不考虑“附件”的问题，那么就是0-1背包问题。 一开始觉得要考虑附件好像整个问题就会变得复杂，还挺头痛的。 但是所谓附件，表面上在制造问题，但是实际上也真的就是“附件”。 2. 化繁为简 我们可以这样 展开全文
去ta的博客 赞 (124) 回复(8) 收起
头像 代码界的小白
发表于 2021-12-03 21:14:56
题目主要信息 1、从m个物品中选出若干个，其总价低于N 2、物品分为主件与附件，如果要买为附件的物品，必须先买该附件所属的主件 3、使得每件物品的价格与重要度的乘积的总和最大 方法一:动态规划 具体方法 本题很明显是一道01背包问题，对于这种问题，我们一般采用动态规划的方法来进行解决。我们定义动规数 展开全文
去ta的博客 赞 (119) 回复(20) 收起
头像 日不落拓海海
发表于 2022-02-15 19:47:28
这一题真的花了我好长时间！！！这一题是01背包问题的衍生，但是多了一个附件的判断，导致这道题很琐碎要考虑很多细节。（感觉要是机考考这道题我完全做不完了） 前提知识背景：01背包问题 （不知道这道题怎么做的可以先把01背包问题看懂https://zhuanlan.zhihu.com/p/1047386 展开全文
去ta的博客 赞 (92) 回复(14) 收起
头像 牛客875694424号
发表于 2021-11-06 21:43:22
看了前面大佬的C++题解，写了一份Java版的 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner( 展开全文
去ta的博客 赞 (71) 回复(18) 收起
头像 牛客779767040号
发表于 2022-03-18 10:31:26
#include <stdio.h> #include <string.h> #define MAX(a,b) ((a>b)?(a):(b)) int main(void) { int N = 0, m = 0; scanf("%d %d",& 展开全文
去ta的博客 赞 (52) 回复(2) 收起
头像 RyouMon
发表于 2021-10-16 20:40:34
参考一位大佬的思路，写出的Python代码 from collections import defaultdict # 处理输入 n, m = map(int, input().split()) n //= 10 # 价格总为 10 的倍数，优化空间复杂度 prices = defaultdic 展开全文
去ta的博客 赞 (45) 回复(6) 收起
头像 陶陶2021
发表于 2021-10-01 00:36:07
1、如果只包含主件，则是经典的01背包问题 2、现在加了附件，则最大值有四种情况：主件、主件+附件1、主件+附件2、主件+附件1+附件2 第一步：记录原始数据 记录每个主件以及其附件的关系，并记录其 价格 * 重要度 第二步：遍历主件 记录主件在四 展开全文
去ta的博客 赞 (42) 回复(5) 收起

问题信息

动态规划
难度：
744条回答 102347浏览

热门推荐

通过挑战的用户

查看代码

相关试题

购物单

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号