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 maxn=51;
var a:array[0..maxn] of string;
    b,d,e,re:array[1..maxn] of longint;
    f:array[0..maxn,0..maxn,-1..maxn] of longint;
    n,x,y,z:longint;
    kq:ansistring;

procedure rf;
var i,t:longint;  c:char; code:integer; s:string;
begin
     readln(n);
     readln(x,y,z);
     for i:=1 to n do
     begin
          readln(a[i]);
          t:=pos(' ',a[i]);
          s:=copy(a[i],t+1,length(a[i])-t);
          delete(a[i],t,length(a[i])-t+1);
          val(s,b[i],code);
     end;
end;

procedure sort;
var i,j,t:longint; p:string;
begin
     for i:=1 to n-1 do
         for j:=i+1 to n do
             if a[i]<a[j] then
             begin
                  p:=a[i]; a[i]:=a[j]; a[j]:=p;
                  t:=b[i]; b[i]:=b[j]; b[j]:=t;
             end;
end;

procedure calc;
var i,j:longint;
begin
     for i:=1 to n do
         for j:=1 to length(a[i]) do
             if a[i,j]='a' then inc(d[i])
             else inc(e[i]);
end;

procedure pr;
var i,j,k,p:longint;
begin
     sort;
     calc;
     f[0,0,-1]:=1;
     for i:=1 to n do
       for j:=d[i] to x do
         for k:=e[i] to y do
           for p:=0 to z do
             if (f[j-d[i],k-e[i],p-1]>0) and (f[j,k,p]<f[j-d[i],k-e[i],p-1]+b[i]) then
                f[j,k,p]:=f[j-d[i],k-e[i],p-1]+b[i];
end;

procedure att(j,k,p:longint);
var i,last:longint; s:ansistring;
begin
     fillchar(re,sizeof(re),0);
     last:=n;
     while p>=0 do
     begin
          for i:=last downto 1 do
              if (d[i]<=j) and (e[i]<=k) and (f[j,k,p]=f[j-d[i],k-e[i],p-1]+b[i]) then
              begin
                   inc(re[i]);
                   j:=j-d[i]; k:=k-e[i]; p:=p-1;
                   last:=i;
                   break;
              end;
     end;
     for i:=n downto 1 do
         for j:=1 to re[i] do
             s:=s+a[i]+' ';
     if s<kq then kq:=s;
end;

procedure trace;
var i,jj,kk,pp,j,k,p,last,res:longint;
begin
     kq:='z';
     res:=0;
     for j:=0 to x do
         for k:=0 to y do
             for p:=-1 to z do
                 if f[j,k,p]>res then
                    res:=f[j,k,p];
     for j:=0 to x do
         for k:=0 to y do
             for p:=-1 to z do
                 if f[j,k,p]=res then att(j,k,p);
     writeln(kq);
end;

begin
     rf;
     pr;
     trace;
end.

Code mẫu của ladpro98

{$H+}
program TRIBE;
uses    math,sysutils;
const   maxn=50;
        fi='';
type    e=record
                a,b,w:longint;
                s:string;
        end;
var     f,choose:array[0..maxn,0..maxn,0..maxn] of longint;
        n,mx,my,mz,d:longint;
        p:array[1..maxn] of e;

procedure input;
var     inp:text;
        i,j:longint;
        s:string;
        te:e;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        readln(inp,mx,my,mz);
        for i:=1 to n do begin
                readln(inp,s);
                for j:=1 to length(s) do begin
                        if s[j] = ' ' then break;
                        if s[j] = 'a' then inc(p[i].a)
                        else inc(p[i].b);
                end;
                p[i].w:=StrToInt(copy(s,j+1,length(s)-j));
                p[i].s:=copy(s,1,j-1);
        end;
        close(inp);
        for i:=1 to n do
        for j:=i+1 to n do
        if p[i].s>p[j].s then begin
                te:=p[i];
                p[i]:=p[j];
                p[j]:=te;
        end;
end;

procedure dp;
var     i,x,y,z:longint;
begin
        for x:=0 to mx do
        for y:=0 to my do
        for z:=1 to mz+1 do
        begin
                for i:=1 to n do
                if (x>=p[i].a) and (y>=p[i].b) and (f[x,y,z]<f[x-p[i].a,y-p[i].b,z-1]+p[i].w) then begin
                        f[x,y,z]:=f[x-p[i].a,y-p[i].b,z-1]+p[i].w;
                        choose[x,y,z]:=i;
                end;
        end;
end;

procedure output;
var     i,x,y,z:longint;
begin
        x:=mx;y:=my;z:=mz+1;
        while choose[x,y,z]>0 do
        begin
                d:=choose[x,y,z];
                dec(x,p[d].a);
                dec(y,p[d].b);
                dec(z);
                write(p[d].s);
                if choose[x,y,z]>0 then write(' ');
        end;
end;

begin
        input;
        dp;
        output;
end.

Code mẫu của RR

{$R+,Q+}
program TRIBE;
const
  FINP='';
  FOUT='';
  MAXN=52;
type
  st=string[MAXN];
var
  a,b,c,n:longint;
  cost,sa,sb:array[1..MAXN] of longint;
  word:array[1..MAXN] of st;
  pre,d:array[0..MAXN,0..MAXN,0..MAXN] of longint;
procedure inp;
var
  ch:char;
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  readln(f,a,b,c);
  for i:=1 to n do
    begin
      repeat
        read(f,ch);
        if ch<>' 'then word[i]:=word[i]+ch;
        if ch='a' then inc(sa[i])
        else if ch='b' then inc(sb[i]);
      until ch=' ';
      readln(f,cost[i]);
    end;
  close(f);
end;
procedure init;
var
  i:longint;
begin
  for i:=1 to MAXN do
    begin
      word[i]:='';
      sa[i]:=0; sb[i]:=0;
      cost[i]:=0;
    end;
end;
procedure solve;
var
  i,aa,bb,u:longint;
begin
  for i:=1 to c+1 do
  begin
    for u:=1 to n do
    for aa:=0 to a do
    for bb:=0 to b do
      if (aa>=sa[u]) and (bb>=sb[u]) then
        if d[i,aa,bb]<d[i-1,aa-sa[u],bb-sb[u]]+cost[u] then
          begin
            d[i,aa,bb]:=d[i-1,aa-sa[u],bb-sb[u]]+cost[u];
            pre[i,aa,bb]:=u;
          end;
  end;
end;
procedure ans;
var
  f:text;
  i,aa,bb,li,la,lb:longint;
  procedure trace(i,a,b:longint);
  var
    u:longint;
  begin
    u:=pre[i,a,b];
    if u=0 then exit;
    write(f,word[u]);
    if i<li+1 then write(f,' ');
    if i>1 then trace(i-1,a-sa[u],b-sb[u]);
  end;
begin
  assign(f,FOUT); rewrite(f);
  li:=0; la:=0; lb:=0;
  for i:=c+1 downto 1 do
  for aa:=0 to a do
  for bb:=0 to b do
    if d[i,aa,bb]>d[li,la,lb] then
      begin
        li:=i;
        la:=aa;
        lb:=bb;
      end;
  if li>0 then trace(li,la,lb);
  close(f);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure swaps(var a,b:st);
var
  temp:st;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  mid:st;
begin
  mid:=word[(l+r) div 2];
  i:=l; j:=r;
  repeat
    while word[i]<mid do inc(i);
    while word[j]>mid do dec(j);
    if i<=j then
      begin
        swaps(word[i],word[j]);
        swap(sa[i],sa[j]);
        swap(sb[i],sb[j]);
        swap(cost[i],cost[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
begin
  init;
  inp;
  sort(1,n);
  solve;
  ans;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,x,y,z,gt[51],soa[51],sob[51],f[51][51][55],temp;
string s[51],the1,the2,the; 

int main(){
     //freopen("TRIBE.in","r",stdin);
     scanf("%d %d %d %d",&n,&x,&y,&z);
     for(int i = 1;i<=n;i++)
          cin>>s[i]>>gt[i];
     memset(f,0,sizeof(f)); 
     for(int i = 1;i<=n;i++)
          for(int j = 1;j<=n;j++){
                the1 = s[i]+' '+s[j];
                the2 = s[j]+' '+s[i];
                if(the1.compare(the2)<0){
                     the = s[i];
                     s[i] = s[j];
                     s[j] = the;
                     temp = gt[i];
                     gt[i] = gt[j];
                     gt[j] = temp;
                }  
          }
     for(int i = 1;i<=n;i++){
          soa[i] = 0; sob[i] = 0;
          for(int j = 0;j<s[i].length();j++)
                if(s[i][j]=='a') soa[i]++;
                else sob[i]++;
     }

     for(int i = 1;i<=z+1;i++){
           for(int tx = 0;tx<=x;tx++)
                 for(int ty=0;ty<=y;ty++){
                      f[tx][ty][i] = f[tx][ty][i-1];
                      for(int j = 1;j<=n;j++)
                           if(tx-soa[j]>=0 && ty-sob[j]>=0)
                                 f[tx][ty][i] >?= f[tx-soa[j]][ty-sob[j]][i-1]+ gt[j];
                 }
     }
     z++;
     int run = f[x][y][z];
     //printf("%d\n",run);
     //while(f[x][y][z] == f[x][y][z-1]) z--;
     int l;
     while(z>0){
           l = z;     
          // printf("%d %d %d %d\n",run,x,y,z);     
           for(int i = 1;i<=n;i++){
                if(x>=soa[i] && y>=sob[i])
                     if(run == f[x-soa[i]][y-sob[i]][z-1]+gt[i]){
                            cout<<s[i]<<" ";
                            run -= gt[i];
                            x -= soa[i];
                            y -= sob[i];
                            z--;
                            break;
                     }
           }
           if(l==z) z--;
          // printf("%d %d %d %d\n",run,x,y,z);
           //getch();
     }
    // getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int f[52][52][52];
vector< pair<string,int> > v;
string s[52];
int a[52],b[52],val[52];
int n,maxx,maxy,maxz;

int rec(int x,int y,int z)
{
     if (f[x][y][z] != -1) return f[x][y][z];
     int best = 0;
     if (!z) 
     {
        for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,val[i]);
     }
     else
       for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,rec(x - a[i],y - b[i],z - 1) + val[i]);
     f[x][y][z] = best;  return best;
};

void track(int x,int y,int z,bool first)
{
     if (!f[x][y][z]) return;
     if (!first) printf(" ");
     if (!z)
     {
       for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i])
       {
           cout << s[i]; break;
       };
     }
     else
     for (int i = 0; i < n; i++) 
       if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i] + rec(x - a[i],y - b[i],z - 1))
       {
             cout << s[i];  track(x - a[i],y - b[i],z - 1,false);  break;       
       };
};

int main()
{
//    freopen("tribe.in","r",stdin);
//    freopen("tribe.ou","w",stdout);
    scanf("%d", &n);
    scanf("%d %d %d", &maxx, &maxy, &maxz);
    for (int i = 0; i < n; i++)
    {
        string st;  int k;
        cin >> st >> k;
        v.push_back(make_pair(st,k));        
    };
    sort(v.begin(),v.end());
    for (int i = 0; i < n; i++)
    {
        a[i] = 0;  b[i] = 0; s[i] = v[i].first; val[i] = v[i].second;
        for (int j = 0; j < s[i].size(); j++) if (s[i][j] == 'a') a[i]++; else b[i]++;
    };
    memset(f,-1,sizeof(f));
    int tmp = rec(maxx,maxy,maxz);
    track(maxx,maxy,maxz,true);  
};

Code mẫu của khuc_tuan

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    static class Word {
        String w;
        int na, nb;
        int value;
    }

    static int n;
    static int x, y, z;
    static Word[] a;
    static int[][][][] F;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        z = sc.nextInt();
        sc.nextLine();
        a = new Word[n];
        for (int i = 0; i < n; ++i) {
            String[] tmp = sc.nextLine().split(" ");
            a[i] = new Word();
            a[i].w = tmp[0];
            a[i].value = Integer.parseInt(tmp[1]);
        }
        Arrays.sort(a, new Comparator<Word>() {
            public int compare(Word w1, Word w2) {
                return w1.w.compareTo(w2.w);
            }
        });
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < a[i].w.length(); ++j)
                if (a[i].w.charAt(j) == 'a')
                    ++a[i].na;
                else
                    ++a[i].nb;
        F = new int[x + 1][y + 1][z + 1][2];
        for (int[][][] a3 : F)
            for (int[][] a2 : a3)
                for (int[] a1 : a2)
                    Arrays.fill(a1, -1);
        System.out.println(truyvet(x, y, z, 0));
    }

    static String truyvet(int x, int y, int z, int need) {
        int res = calc(x, y, z, need);
        // if (z > 0 && res == calc(x, y, z - 1, 0))
        // return " " + truyvet(x, y, z - 1, 0);
        for (int k = 0; k < a.length; ++k) {
            if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
                int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
                if (res == now + a[k].value)
                    return (need == 0 ? "" : " ") + a[k].w
                            + truyvet(x - a[k].na, y - a[k].nb, z - need, 1);
            }
        }
        return "";
    }

    static int calc(int x, int y, int z, int need) {
        if (F[x][y][z][need] != -1)
            return F[x][y][z][need];

        int res = 0;
        // if (z > 0)
        // res = Math.max(res, calc(x, y, z - 1, 0));

        for (int k = 0; k < a.length; ++k)
            if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
                int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
                res = Math.max(res, now + a[k].value);
            }

        return F[x][y][z][need] = res;
    }
}