Author: lllyouo
Date: 20250225
tag: 完全背包
link: http://ybt.ssoier.cn:8088/problem_show.php?pid=1273

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 25, M = 4010;
int n, m, a[N];
// 考虑从前 i 种货币中选择货币凑成 j 元的方案数
long long f[N][M];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];

	// 不选任何货币，凑成 0 元的方案数为 1
	for (int i = 1; i <= n; i++) f[i][0] = 1;	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j >= a[i]) f[i][j] = f[i - 1][j] + f[i][j - a[i]]; // 选择第 i 种货币
			else f[i][j] = f[i - 1][j]; // 不选第 i 种货币
		}
	}
	cout << f[n][m] << endl;
	
	return 0;
}