洛谷P1164 小A点菜 && caioj 1410 动态规划1：点菜（背包方案问题）

方程很简单

f[0] = 1

f[j] += f[j-w[i]]

#include<cstdio>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXM = 11234;

const int MAXN = 112;

int f[MAXM], w[MAXN];

int m, n;

int main()

{

	scanf("%d%d", &n, &m);

	REP(i, 0, n) scanf("%d", &w[i]);

	f[0] = 1;

	REP(i, 0, n)

		for(int j = m; j >= w[i]; j--)

			f[j] += f[j-w[i]];

	printf("%d\n", f[m]);

	return 0;

}

巴特西

洛谷P1164 小A点菜 && caioj 1410 动态规划1：点菜（背包方案问题）

最新文章

热门文章