本題是一個完全背包問題，需要對三重循環進行優化。
容易想到用(i, j)表示從前i個硬幣中選取總價值為j的方案中，使用硬幣數目的集合。f(i, j)表示其最小值。
則有 f(i, j) = min(f(i - 1, j - k*w[i]) + k), 其中 k = {0, 1, ..., j / w[i]}，w[i]是第i個硬幣的價值。
于是本題在對i,j循環之外還要額外對k循環，一定會超時。需要進行優化。

我們發現，由
f(i, j) = min(f(i - 1, j - k*w[i]) + k), 其中 k = {0, 1, ..., j / w[i]} (1)

可得
f(i, j - w[i]) = min(f(i - 1, j - (k + 1)*w[i]) + k), 其中 k = {0, 1, ..., j / w[i]} (2)

把(2)代入(1)，可得
f(i, j) = min(f(i - 1, j), f(i, j - w[i]) + 1)
優化完成

下面給出代碼，使用滾動數組優化（不用滾動數組也能過）。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int M = 25, N = 50010;

int f[N];
int w[M];

int main(){
	int n, m;
	cin>>n>>m;
	
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	
	for(int i = 1; i <= m; i++) cin>>w[i];
	
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			if(j >= w[i]) f[j] = min(f[j], f[j - w[i]] + 1);
	
	cout<<f[n];
	
	return 0;
}