Đề bài:

• http://vn.spoj.com/problems/DTDOI/

Thuật toán:

• Thông thường thì ta sẽ có cách giải QHĐ với đpt O(S*n), nhưng vì S lên đến 1e9 nên ta có cách làm như sau:
  -Giảm S bằng tờ có giá trị lớn nhất cho đến khi S đủ nhỏ để QHĐ (giảm đến mức nào thì các bạn nên tự thử, trong code mình giảm xuống 100000)
  -QHĐ

Code:

• xem code trên ideone

#include
using namespace std;
int n,s;
int a[101];
int d[100001];
int main()
{
	cin>>n>>s;
	for (int i=1; i <= n; i++)
		cin>>a[i];
	int mx=0;
        for (int i=1; i <= n; i++)
                mx=max(mx,a[i]);
	int res=0;
	while (s >= 100001)
		{
			res++;
			s-=mx;
		}
	d[0]=0;
	for (int i=1; i <= s; i++)
		{
                        d[i]=10000000;
                        for (int j=1; j <= n; j++)
			        if (i >= a[j])
				         d[i]=min(d[i],d[i-a[j]]+1);
                }
	cout<