洛谷--P1164

题目背景

   uim

神犇拿到了

uoi

的

ra

（镭牌）后，立刻拉着基友

小A

到了一家……餐馆，很低端的那种。

uim

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

题目描述

        不过

uim

由于买了一些

辅（e）辅（ro）书

，口袋里只剩MM元(M \le 10000)(M≤10000)。

餐馆虽低端，但是菜品种类不少，有NN种(N \le 100)(N≤100)，第ii种卖a_iai​元(a_i \le 1000)(ai​≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

   小A

奉行“不把钱吃光不罢休”，所以他点单一定刚好吧

uim

身上所有钱花完。他想知道有多少种点菜方法。

           由于

小A

肚子太饿，所以最多只能等待11秒。

输入格式

        第一行是两个数字，表示NN和MM。

        第二行起NN个正数a_iai​（可以有相同的数字，每个数字均在10001000以内）。

输出格式

         一个正整数，表示点菜方案数，保证答案的范围在intint之内。

输入输出样例

输入 #1复制

4 4
1 1 2 2
           

输出 #1复制

3
           

          感觉自己真是个笨比。哎。

方法一（暴力）：

        之前写过一道类似的题，然后直接上去我就用来暴力枚举的方法，寻找所有的可以正好花完钱的情况。大概思路就是从前往后找一直用for循环，然后知直到跑完整个数组，或者花掉的钱大于M结束，而且这个说每种菜只有一道，所以说就是只能选择，不能向前选择。（然后写之前那个题的时候不知道咋搞，因为for循环嵌套的个数是不一定的，所以不会写，还是去题解区看了大佬的代码），因为for循环嵌套的个数是不一定的，所以我们势必要用到递归函数，给函数提供一个已经花掉的钱（sum1），还有已经选的菜的最大编号的下一位（start）来告诉函数循环从哪里开始，然后去直接去交了

代码如下：

#include <iostream>
using namespace std;
int arr[101];
int sum = 0;
int n, m;
void func(int start, int sum1)
{
	if (sum1 == m)
	{
		sum++;
		return;
	}
	if (start == n || sum1 > m)
		return;
	for (int i = start; i < n; i++)
	{
		func(i + 1, sum1 + arr[i]);
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	} 
	func(0, 0);
	cout << sum;
	return 0;
}
           

       完了只得了90分，有一个数据时间太长了。 

       不成器的我又去看了大佬的题解，结果发现这题其实不难其实就跟那个01背包好像。然后听我啰嗦一下。

方法二：

      类似于01背包我们首先要具有一个想法，也就是说在我们钱数为j 的情况下，选不选第i种菜取决于我们的钱够不够 （我们用value[i]数组储存菜的价格，用arr[i][j]数组来储存在我们钱数为j，可以选的菜的编号为0-->i 时的种类）动态规划。

      1、当我们的钱不够的时候  : j<value[i]

               此时我们用钱数j在编号1--->i上和编号1--->i-1上的种类是一样的 即：arr[i][j]=arr[i-1][j];

       2 、当我们的钱可以买第i个菜的时候    j>=value[i]

             （1）、当我们的钱大于value[i]的时候    j>value[i]

                         我们的选择有买和不买，所以此时种类为买和不买的和,当我们买的时候的种类数与arr[i-1][j-value[i]]的种类数一样。即：

                       arr[i][j]=arr[i-1][j]+arr[i-1][j-value[i]];  

               (2)、当我们的钱正好等与第i道菜的钱的时候    j=value[i]

                        想想，在用j的钱去买1--->i-1的菜的时候我们有arr[i-1][j]种方法，在买1---->i的时候我们由多一种（用全部的钱买第i道菜），而且这种方法与之前的都不一样，所以

                       arr[i][j]=arr[i-1][j]+1;

        聪明的大佬又已经想到了我们的这三个转态转移方程中arr[i][j]只与上一行的数据有关，所以我们依旧可以把它压缩为一维数组（我就不说了，在01背包里说过了）。差点忘了说了，这个更新数组的时候要用到之前的值，所以数组要从最后开始更新！！！

具体代码如下：

#include <iostream>
using namespace std;
int value[1001], arr[1001];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> value[i];
	} 
	cout << "----------------------" << endl;
	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= 1; j--)
		{
			if (j > value[i])
			{
				arr[j] = arr[j] + arr[j - value[i]];
		    }
			if (j == value[i])
			{
				arr[j] = arr[j] + 1;
			}
		}
		for (int k = 1; k <= m; k++)
		{
			cout << arr[k] << " ";
		}
		cout << endl;
	}
	return 0;
}
           

示例的运行结果如下：