首页 > 试题广场 >

购物单

[编程题]购物单
  • 热度指数：476626 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。
\hspace{23pt}\bullet\,主件可以没有附件，至多有 2 个附件。附件不再有从属于自己的附件。
\hspace{23pt}\bullet\,若要购买某附件，必须先购买该附件所属的主件，且每件物品只能购买一次。

\hspace{15pt}王强查到了 m 件物品的价格，而他只有 n 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 1 \sim 5 表示。他希望在不超过预算的前提下，使满意度最大。

\hspace{15pt}满意度定义为所购每件物品价格与重要度乘积之和。具体地说，记第 i 件物品的价格为 v_i，重要度为 w_i；若共选中 k 件物品，编号为 j_1,j_2,\dots,j_k，则满意度计算为：
\sum\limits_{t=1}^{k} v_{j_t} \times w_{j_t} = v_{j_1} w_{j_1} + v_{j_2} w_{j_2} + \dots + v_{j_k} w_{j_k}

\hspace{15pt}请你帮助王强计算可获得的最大的满意度。

输入描述:
\hspace{15pt}第一行输入两个整数 n, m \left(1 \leqq n \leqq 3 \times 10^4;\ 1 \leqq m \leqq 60\right) 代表预算、查询到的物品总数。
\hspace{15pt}此后 m 行，第 i 行输入三个整数 v_i, w_i, q_i \left(1 \leqq v_i \leqq 10^4;\ 1 \leqq w_i \leqq 5;\ 0 \leqq q_i \leqq m\right) 代表第 i 件物品的价格、重要度、主件编号。特别地，q_i = 0 代表该物品为主件，否则表示该附件从属于主件 q_i。编号即输入顺序，从 1 开始。

\hspace{15pt}特别地，保证全部物品的价格 v 均为 10 的倍数；且每个主件的附件数不超过 2 个。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表王强可获得的最大满意度。
示例1

输入

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

输出

130

说明

\hspace{15pt}在这个样例中，第三、四、五件物品为主件，第一、二件物品为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。
\hspace{15pt}我们可以证明，购买一、二、五件商品，获得的满意度最大，为 20 \times 3 + 20 \times 3 + 10 \times 1 = 130。
示例2

输入

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

输出

2200

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

问题信息

动态规划
难度：
776条回答 104717浏览

热门推荐

通过挑战的用户

查看代码

相关试题

购物单

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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