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

分析：01背包+加法原理。
如果是一维的话，f[] 表示的是以及价格多少是方案,f[i] 价格为i时，方案数是多少。
那么 状态转移方程就是 f[v] += f[v-w[i]] 
为什么是加呢，第一题目要求求方案总数，
第二因为既然有价格是w[i]的菜，这就说明价格是 v-w[i] 时，再选上这份菜价格刚好是v，所以：价格 v　的方案数加上价格 v-w[i] 的方案总数就是价格 v 的方案总数。
f[v] += f[v-w[i]];

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int f[10010];
 6 int w[110];
 7 int n,m;
 8 int main()
 9 {
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;++i)
12         scanf("%d",&w[i]);
13     f[0] = 1; 
14     for(int i=1;i<=n;++i)
15     {
16         for(int v=m;v>=w[i];--v)
17         {
18             f[v] += f[v-w[i]];
19         }
20     }
21     printf("%d",f[m]);
22     return 0;
23 }

二维，也可以做。f[i][v] 表示选择了 i 件物品，价格刚好是v是方案总数。

f[i][v] = f[i-1][v]+f[i-1][v-w[i]];

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int f[110][10010];
 6 int w[110];
 7 int n,m;
 8 
 9 int main()
10 {
11     scanf("%d%d",&n,&m);
12     for(int i=1;i<=n;++i)
13         scanf("%d",&w[i]);
14     f[0][0] = 1;
15     for (int i=1;i<=n;++i)
16     { 
17         for (int v=0;v<=m;++v)
18         {
19             if (v>=w[i]) f[i][v] = f[i-1][v]+f[i-1][v-w[i]];
20             else f[i][v] = f[i-1][v];
21         }
22     }
23     printf("%d",f[n][m]);
24     return 0;
25 }