P1164 小A点菜问题的实验报告
时间: 2023-11-16 11:04:49 浏览: 41
这道题目是一道经典的背包问题,要求从给定的 n 种菜品中选出若干个菜品,使得它们的价格之和恰好为 m。
我们可以使用动态规划的方法来解决这个问题。具体来说,我们可以定义一个二维数组 f[i][j],表示从前 i 种菜品中选,总价值恰好为 j 的方案数。初始状态为 f[0][0] = 1,表示从 0 种菜品中选出总价值为 0 的方案数为 1(即不选任何菜品)。
然后,我们可以使用状态转移方程 f[i][j] = f[i-1][j] + f[i-1][j-a[i]],表示要么不选第 i 种菜品,此时方案数为 f[i-1][j];要么选第 i 种菜品,此时方案数为 f[i-1][j-a[i]],因为选了这个菜品后,剩余的价值就是 j-a[i]。
最后,我们输出 f[n][m],即从 n 种菜品中选出总价值恰好为 m 的方案数。
下面是 AC 代码和一些细节处理的实现建议:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;
const int MAXM = 10005;
int f[MAXN][MAXM]; // f[i][j] 表示从前 i 种菜品中选,总价值恰好为 j 的方案数
int a[MAXN]; // a[i] 表示第 i 种菜品的价格
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(f, 0, sizeof(f)); // 初始化为 0
f[0][0] = 1; // 初始状态
for (int i = 1; i <= n; i++) {
for (int j = a[i]; j <= m; j++) { // 注意这里要从 a[i] 开始枚举
f[i][j] = f[i-1][j] + f[i-1][j-a[i]]; // 状态转移方程
}
}
cout << f[n][m] << endl; // 输出最终答案
return 0;
}
```
需要注意的细节有:
1. 状态转移方程中,第二个下标 j 要从 a[i] 开始枚举,因为如果 j < a[i],则选第 i 种菜品的话,总价值就会小于 a[i],不符合题意。
2. 初始状态要赋值为 1,因为从 0 种菜品中选出总价值为 0 的方案数只有一种(即不选任何菜品)。
3. 可以使用 memset 函数将 f 数组初始化为 0。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)