Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxc=100000;
var n,s,re:longint;
    a:array[1..100] of longint;
    d:array[1..100] of byte;
    f:array[0..1,0..maxc] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n,s);
     fillchar(d,sizeof(d),0);
     for i:=1 to n do
     begin
          read(t); d[t]:=1;
     end;
     t:=0;
     for i:=1 to 100 do
         if d[i]>0 then
         begin
              inc(t); a[t]:=i;
         end;
     close(input);
end;

procedure knap;
var i,j,k,cur:longint;
begin
     for i:=0 to maxc do f[1,i]:=i;
     for i:=2 to n do
     begin
          cur:=i mod 2;
          f[cur]:=f[1-cur];
          for j:=1 to maxc do
              if (j>=a[i]) and (f[cur,j]>f[cur,j-a[i]]+1) then
                 f[cur,j]:=f[cur,j-a[i]]+1;
     end;
end;

procedure pr;
var i,j:longint;
begin
     knap;
     if s>maxc then
     begin
          re:=(s-maxc) div a[n];
          if (s-maxc) mod a[n]<>0 then inc(re);
          s:=s-re*a[n];
     end;
     re:=re+f[n mod 2,s];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000

int n, a[105], f[22222], s;

int main() {
    scanf("%d%d",&n,&s); rep(i,n) scanf("%d",a+i); sort(a,a+n);
    int add = 0;
    if(s >= 20000) {
        add = (s - 20000) / a[n-1];
        s -= add * a[n-1];
    }
    fo(i,1,s) {
        f[i] = INF;
        for(int j = 0; a[j] <= i && j < n; ++j)
            f[i] = min(f[i], f[i-a[j]]+1);
    }
    printf("%d\n", f[s] + add);
    return 0;
}

Code mẫu của ladpro98

program dtdoi;
uses    math;
const   maxn=111;
        maxV=10000;
        oo=1234567890;
        fi='';
var     a:array[1..maxn] of longint;
        f:array[0..maxn,0..maxV] of longint;
        n,s,maxA,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,s);
        for i:=1 to n do
        begin
                read(inp,a[i]);
                maxA:=max(maxA,a[i]);
        end;
        close(inp);
end;

procedure process;
var     i,j,t:longint;
begin
        //greedy
        if s>maxV then
        begin
                t:=(s-maxV) div maxA;
                s:=s-maxA*(t+1);
                res:=t+1;
        end;
        //dp
        f[0,0]:=0;
        for j:=1 to s do
        f[0,j]:=oo;
        for i:=1 to n do
        for j:=1 to s do
        begin
                f[i,j]:=f[i-1,j];
                if j>=a[i] then
                f[i,j]:=min(f[i,j],f[i,j-a[i]]+1);
        end;

end;

begin
        input;
        process;
        write(res+f[n,s]);
end.

Code mẫu của RR

//Written by RR
{$R+,Q+}
{$Mode objfpc}
{$inline on}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       20111;

var
  f1,f2         :       text;
  n,s           :       longint;
  a             :       array[1..111] of longint;
  f             :       array[0..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n,s);
      for i:=1 to n do
        read(f1,a[i]);
    end;

procedure solve;
    var
      i,k:longint;
    begin
      fillchar(f,sizeof(f),$77);
      f[0]:=0;
      for i:=1 to MAXN do
      for k:=1 to n do
        if a[k]<=i then
          f[i]:=min(f[i],f[i-a[k]]+1);

      if s<=MAXN then
        writeln(f2,f[s])
      else
        begin
          k:=0;
          for i:=1 to n do
            k:=max(k,a[i]);
          i:=MAXN;
          while i mod k<>0 do dec(i); i:=i-k+s mod k;
          writeln(f2,f[i]+(s-i) div k);
        end;
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int main()
{
    int n,a[101],S,max = 0,f[10001];
    scanf("%d %d",&n,&S);
    for(int i = 1;i<=n;i++)
    {
       scanf("%d",&a[i]);
       if(a[i]>max)
          max = a[i];
    }
    int KQ = 0;
    if(S>10000)
    {
        int d = (S-10000)/max+1;
        S = S - max*d;
        KQ = KQ+d;
    }
    f[0] = 0;
    for(int i = 1;i<=S;i++)   
    {
        f[i] = 10000;max = 0;
        for(int j = 1;j<=n;j++)
        {
            if(i>=a[j] && f[i]>f[i-a[j]]+1)
                 f[i] = f[i-a[j]]+1;
        }
    }
    KQ = KQ + f[S];
    printf("%d",KQ);
   // getch();
}

Code mẫu của ll931110

#include <iostream>
#define MAXN 101
#define MAXV 10000
#define MAXK 1000000000
using namespace std;

int F[MAXV],a[MAXN],n,s;

int main()
{
    int i,j,k,max,res;

    //freopen("dtdoi.inp","r",stdin);
    //freopen("dtdoi.out","w",stdout);

    scanf("%d%d", &n, &s);
    max = 0;
    for (i = 1; i <= n; i++) 
      {
           scanf("%d", &a[i]);
           if (max < a[i] && a[i] <= s) max = a[i];
      }

    for (i = 0; i < MAXV; i++) F[i] = MAXK;
    F[0] = 0;

    for (i = 1; i < MAXV; i++)
      for (j = 1; j <= n; j++)
        if (i >= a[j])
          if (F[i] > F[i - a[j]] + 1) F[i] = F[i - a[j]] + 1;

    if (s >= MAXV)
    {
          k = ((s - MAXV) / max) + 1;
          s -= k * max;
    }
    else k = 0;

    res = MAXK;
    do
    {
        if (res > k + F[s]) res = k + F[s];
        k++;
        s -= max;
    }
    while (s >= 0);

    printf("%d", res);
}

Code mẫu của skyvn97

#include<cstdio>
#include<algorithm>
#define MAX   111
using namespace std;
const int mdp=60000;
int n,s,mv;
int v[MAX];
int f[MAX][mdp];
void init(void) {
    scanf("%d",&n);
    scanf("%d",&s);
    int i;
    mv=-1;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&v[i]);
        if (v[i]>mv) mv=v[i];
    }
    sort(&v[1],&v[n+1]);
}
int min(const int &x,const int &y) {
    if (x<y) return (x); else return (y);
}
void optimize(void) {
    int i,j;
    for (i=1;i<=n;i=i+1) f[i][0]=0;
    for (i=1;i<mdp;i=i+1) f[1][i]=i;
    for (i=2;i<=n;i=i+1)
        for (j=1;j<mdp;j=j+1) {
            if (j<v[i]) f[i][j]=f[i-1][j];
            else f[i][j]=min(f[i-1][j],f[i][j-v[i]]+1);
        }           
}
void answer(void) {
    if (s<mdp) {
        printf("%d",f[n][s]);
        return;
    }
    int i;
    int best=(int)1e9;
    for (i=s/mv;i>=0;i=i-1) {
        if (s-mv*i>=mdp) break;
        best=min(best,i+f[n][s-mv*i]);
    }
    printf("%d",best);
}
int main(void) {
    init();
    optimize();
    answer();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

#define MAX 100000

int n, s;
int a[111];
int F[MAX + 10];
int main() {
    scanf("%d%d", &n, &s);
    for(int i=0;i<n;++i) scanf("%d", a + i);
    memset( F, 0x1f, sizeof(F));
    F[0] = 0;
    for(int i=0;i<MAX;++i) {
        for(int j=0;j<n;++j)
            if(i + a[j] <= MAX)
                F[i + a[j]] <?= F[i] + 1;
    }
    if(s <= MAX) cout << F[s] << endl;
    else {
        int best = 1000000000;
        for(int i=0;i<MAX;++i)
            for(int j=0;j<n;++j)
                if((s - i) % a[j] == 0)
                    best <?= F[i] + (s - i) / a[j];
        cout << best << endl;
    }
    // system("pause");
    return 0;   
}