？算法1-4 小A点菜

题目形貌

不外 uim 由于买了一些书，口袋里只剩 M 元 (M≤10000)。
餐馆虽低端，但是菜品种类不少，有 N 种 (N≤100)，第 i 种卖 ai​ 元 (ai​≤1000)。由于是很低端的餐馆，以是每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，以是他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，以是最多只能等候 1 秒。
输入格式

第一行是两个数字，表现 N 和 M。
第二行起 N 个正数 ai​（可以有雷同的数字，每个数字均在 1000 以内）。
输出格式

一个正整数，表现点菜方案数，保证答案的范围在 int 之内。
输入输出样例

输入 #1

1. 4 4
2. 1 1 2 2

复制代码

输出 #1

1. 3

复制代码

方法1：dfs （会有一个测试点超时）

1. #include<iostream>
2. using namespace std;
4. int n, m;
5. int a[110];  //存储每份菜的价格
6. int mark[110];  
7. int ans;
9. void dfs(int step, int flag)
10. {
11.         if(step > m) return;
12.         if(step == m)
13.         {
14.                 ans++;
15.                 return;
16.         }
17.         for(int i=flag; i<n; i++)
18.         {
19.                 if(mark[i] == 0)  //没有被使用过
20.                 {
21.                         mark[i] = 1;
22.                         dfs(step+a[i], i);
23.                         mark[i] = 0;
24.                 }
25.         }
26. }
28. int main()
29. {
30.         cin>>n>>m;
31.         for(int i=0; i<n; i++)
32.         {
33.                 cin>>a[i];
34.         }
35.        
36.         dfs(0, 0);
37.        
38.         cout<<ans;
39.        
40.         return 0;
41. }

复制代码

 方法2：背包
0元可以不点菜，算一种点菜方式 
但是j=0表现没有菜品，不能点，以是是0

1. #include<iostream>
2. using namespace std;
4. int n, m;
5. int a[110];  //存储每个菜的价格
6. int dp[10010][110];  //dp[i][j] i表示总共的钱数 ，j表示一共可以点多少道菜
8. int main()
9. {
10.         cin>>n>>m;
11.        
12.         for(int j=1; j<=n; ++j)
13.         {
14.                 cin>>a[j];
15.         }
16.        
17.         //为dp赋值  
18.         for(int j=0; j<=n; ++j)
19.         {
20.                 //0元可以不点菜，算一种点菜方式
21.                 dp[0][j] = 1;
22.         }
23.        
24.         for(int i=1; i<=m; ++i)
25.         {
26.                 for(int j=1; j<=n; ++j)
27.                 {
28.                         //第i个菜的价格高于总共的钱数 ，则不能点这个菜
29.                         if(a[j] > i) dp[i][j] = dp[i][j-1];
30.                        
31.                         //第i个菜的价格低于于总共的钱数，两种情况：不点这个菜  点这个菜
32.                         else dp[i][j] = dp[i][j-1] + dp[i-a[j]][j-1];
33.                 }
34.         }
35.         cout<<dp[m][n];
36.        
37.         return 0;
38. }

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。