一道好像是动态规划的题,但是推导不出来,求大佬解惑
题目:已知有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