洛谷 P1164 小A点菜 --背包问题求方案数

由于所有的菜品都只能够选一次 所以这就是一个朴实无华的01背包

其实这是一个很好的摸板题
首先我们知道 01背包的一般动态规划方程f[i][j] = max(f[i - 1][j], f[i - 1][j - 1])
由于 i 是线性的所以我们可以优化到f[j] = max(f[j], f[j - 1])
那么这个题其实就是 01背包求方案数

• 因为每次得到的 max 中的是当前的 V 可以装下多少的 物品M
• 那么我们转换一下，假设不要钱的话我们一定可以拿一个那么f[0] = 1；
• 然后我们只要依次加上前面的状态下能购买的数目 然后一起加起来就可以了
• 于是我们就可以得到f[j] += f[j - 1]就是所有的方案数
• 最后只要 cout << f[m] m 为总共的钱数

At Last:
The ac Code is:

#include 

using namespace std;
const int N = 1010;
int f[N];
int n, m;

int main()
{
	cin >> n >> m;
	while(n --)
	{
		int x;
		cin >> x;
		f[0] = 1;
		for (int i = m; i >= x; --i)
			f[i] += f[i - x];
	}
	cout << f[m];
	return 0;
}