标题:一道好像是动态规划的题,但是推导不出来,求大佬解惑
只看楼主
小菜菜学编程
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2023-3-14
结帖率:0
已结贴  问题点数:20 回复次数:2 
一道好像是动态规划的题,但是推导不出来,求大佬解惑
题目:
已知有n件商品,每件商品都有一个价格和一个满意度 ==> 第i件商品具有 price[i] 和 value[i]
小明共有x元钱,想要获得当前能够买到的最多的满意度,请问该怎么买?

规则:当小明原价买了第i件商品后,他拥有一次半价购买第i+1件商品的机会,如果他半价购买了第i+1件商品,那么第i+2件商品就必须原价购买。

样例:输入:n=4,x=5,商品价格数组price[4]=[1,2,3,4],商品满意度数组value[4]=[2,4,4,5]
输出:最大满意度为10
搜索更多相关主题的帖子: 商品 动态 value 推导 数组 
2023-03-14 13:34
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:20 
题目好多地方不明,略

先全价买第一个,花费1元,剩余4元,获得满意度2
再全价买第二个,花费2元,剩余2元,获得满意度4
半价买第个,花费2元,剩余0元,获得满意度5
那么最大满意度应该是11
2023-03-14 16:21
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
所以,题目中的这个 i 是购买顺序的次序,还是价格数组的下标?
2023-03-14 16:23



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-511536-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 1.075691 second(s), 7 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved