Luogu P1164 小A点菜(DP背包)

P1164 小A点菜

题目背景

uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。

uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩M元（M<=10000）。

餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i种卖ai元（ai<=1000）。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待1秒。

输入输出格式

输入格式：

第一行是两个数字，表示N和M。

第二行起N个正数ai（可以有相同的数字，每个数字均在1000以内）。

输出格式：

一个正整数，表示点菜方案数。

输入输出样例

输入样例#1：

4 4
1 1 2 2

输出样例#1：

　　3

　　这道题的数据挺水的。dfs都可以水过去。

　　不过还是要讲一下dp。

　　转移方程: f[j] = f[j] + f[j-a[i]]

　　边界条件: f[0] = 1

　　接下来是代码，首先是dp

 1 #include <cstdio>
 2 
 3 int f[10005];
 4 
 5 int main()
 6 {
 7     int n, m;
 8     int a[105];
 9     scanf("%d%d", &n, &m);
10     for(int i=1; i<=n; i++)
11         scanf("%d", a+i);
12     f[0] = 1;    //0元时候能买空气吃 仅这一种方案
13     for(int i=1; i<=n; i++)
14     {
15         for(int j=m; j>=a[i]; j--)
16         {
17             f[j] = f[j] + f[j-a[i]];
18         }
19     }
20     printf("%d", f[m]);
21     return 0;
22 }

　　这里是dfs:

 1 #include <cstdio>
 2 
 3 int n, m, a[105], ans, visit[105];
 4 
 5 void dfs(int s, int sum)
 6 {
 7     if(sum >= m)
 8     {
 9         if(sum==m)
10             ans++;
11         return;
12     }
13     for(int i=s; i<=n; i++)
14     {
15         if(!visit[i])
16         {
17             visit[i] = 1;
18             dfs(i,sum+a[i]);
19             visit[i] = 0;
20         }
21     }
22 }
23 
24 
25 int main()
26 {
27     scanf("%d%d", &n, &m);
28     for(int i=1; i<=n; i++)
29     {
30         scanf("%d", a+i);
31     }
32     dfs(1, 0);
33     printf("%d", ans);
34     return 0;
35 }