| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 528 人关注过本帖
标题:一道好像是动态规划的题,但是推导不出来,求大佬解惑
只看楼主 加入收藏
小菜菜学编程
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
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册: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
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
所以,题目中的这个 i 是购买顺序的次序,还是价格数组的下标?
2023-03-14 16:23
快速回复:一道好像是动态规划的题,但是推导不出来,求大佬解惑
数据加载中...
 
   



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

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