点菜问题
“因为疫情问题，某公司员工就餐时需通过APP点外卖。每次点外卖的报销金额最大为M元，有N种菜品可以点，每种菜i都有一个评分Pi（即表示菜的受欢迎程度），每种菜i的价格为Vi。现该公司员工如何选择各种菜，能够在报销额度范围内使点到的菜的总评分最大。注意：由于营养均衡的需要，每种菜只能点一次。
输入数据：整数M、N以及每种菜的价格和评分，M表示能够报销的额度，N表示可选择的菜的种类数目。
输出数据：所点菜的最大评分
（1）写出解决此问题所用到的算法及算法设计思想。
动态规划算法求解。
算法设计思想：
a. 分析问题，问题具备最优子结构性质
b. 建立求解问题的递归公式：
f(i, j)表示当报销金额为j，可选择菜品为i, i+1,…., n时点菜问题的最优值。
求解f(i, j)的递归式如下：
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释文章来源：https://www.toymoban.com/news/detail-518722.html
c. 依据上面的递归式，以自底向上方式进行计算，可用二维数组f[][]来存储f(i, j)的相应值。当最后求出f(1,n)时，就解决问题，即f(1,n)为问题的最优值（所点菜的最大评分）
文章来源地址https://www.toymoban.com/news/detail-518722.html
到了这里，关于点菜问题动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
