【算法】算法之点菜问题（C++源码）

【算法】算法之点菜问题（C++源码）

• ​​一、任务描述​​
• ​​二、例子​​
• ​​三、步骤描述​​
• ​​四、运行结果截图​​
• ​​五、源代码（C++）​​

一、任务描述

某实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点。经过长时间的点菜，实验室对于每种菜i都有一个量化的评价分数（表示这个菜的可口程度），为Vi，每种菜的价格为Pi。问如何选择各种菜，才能在报销额度内使点到的菜的总评价最大。注意：由于需要营养多样化，每种菜只能点一次。请设计算法求解上述点菜问题，并使用下页中的数据测试你的算法。

二、例子

C = 90, N = 4：

三、步骤描述

定义三个一维数组，v[]存储的是菜的评价分数，p[]存储的是菜的价格，先输入能报销的总价，输出能点的菜的总数，在比较过程中，用第三个一维数组存储能被报销的价格的最大值分数，下标为每次减去能报菜的单个价格。最后输出最后的c[sum]的总分。

四、运行结果截图

五、源代码（C++）

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
    int sum,n;
    int v[100],p[10],c[100]={0};
    cout<<"Please enter the total reimbursement price : ";
    cin>>sum;
    cout<<"Number of dishes to choose : ";
    cin>>n;
    cout<<endl;
    for(int i=1;i<=n;++i)
    {
        cout<<"The price of the "<<i<<" dish : ";
        cin>>p[i];
        cout<<"The score of the "<<i<<" dish : ";
        cin>>v[i];
        cout<<endl;
        for(int j=sum;j>=p[i];--j)
        {
            c[j]=max(c[j-p[i]]+v[i],c[j]);
        }
    }
    cout<<"In the case of the largest reimbursement, the highest score is obtained : "<<c[sum]<<endl;
    return 0;
}