1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdlib.h>

int porownaj_int(const void *i1, const void *i2)
{
    return *(int *)i2 - *(int *)i1;
}
int main()
{
    int i, j, kont, ile_przedm, ile_plec, l_plec, dalej, wynik, jest, przedm, plec, waga[24], udzwig[100], plecak[24];
    long long razem, razem_waga, razem_udzwig, w_plecaku[100];

    scanf("%d%d", &ile_przedm, &ile_plec);
    for (razem_waga = i = 0; i < ile_przedm; i++)
    {
        scanf("%d", &waga[i]);
        razem_waga += waga[i];
        plecak[i] = -1;
    }
    for (razem_udzwig = i = 0; i < ile_plec; i++)
    {
        scanf("%d", &udzwig[i]);
        razem_udzwig += udzwig[i];
        w_plecaku[i] = 0;
    }
    qsort(waga, ile_przedm, sizeof(int), porownaj_int);
    qsort(udzwig, ile_plec, sizeof(int), porownaj_int);
    if (waga[0] <= udzwig[0] && razem_waga <= razem_udzwig)
    {
        for (l_plec = 1, plec = razem = 0; plec < ile_plec; plec++)
        {
            razem += udzwig[plec];
            if (razem < razem_waga)
                l_plec++;
            else
                break;
        }
        for (dalej = 1; dalej && l_plec <= ile_plec;)
        {
//            printf("%d\n", l_plec);
            for (kont = 1, przedm = 0; kont && przedm < ile_przedm;)
            {
                for (jest = plec = 0; !jest && plec < l_plec; plec++)
                    if (waga[przedm] + w_plecaku[plec] <= udzwig[plec])
                    {
                        plecak[przedm] = plec;
                        w_plecaku[plec] += waga[przedm];
                        jest = 1;
                    }
                if (jest)
                    przedm++;
                else
                    kont = 0;
            }
            if (kont)
                dalej = 0;
            else
            {
                while (dalej && przedm >= 0)
                {
                    for (przedm--; przedm >= 0 && plecak[przedm] == l_plec; przedm--)
                    {
                        plec = plecak[przedm];
                        w_plecaku[plec] -= waga[przedm];
                        plecak[przedm] = -1;
                    }
                    if (przedm >= 0)
                    {
                        plec = plecak[przedm];
                        w_plecaku[plec] -= waga[przedm];
                        plecak[przedm] = -1;
                        for (jest = 0, plec++; !jest && plec < l_plec; plec++)
                            if (waga[przedm] + w_plecaku[plec] <= udzwig[plec])
                            {
                                plecak[przedm] = plec;
                                w_plecaku[plec] += waga[przedm];
                                jest = 1;
                            }
                        if (jest)
                        {
                            for (kont = 1, przedm++; kont && przedm < ile_przedm; przedm++)
                            {
                                for (jest = plec = 0; !jest && plec < l_plec; plec++)
                                    if (waga[przedm] + w_plecaku[plec] <= udzwig[plec])
                                    {
                                        plecak[przedm] = plec;
                                        w_plecaku[plec] += waga[przedm];
                                        jest = 1;
                                    }
                                if (!jest)
                                    kont = 0;
                            }
                            if (kont)
                                dalej = 0;
                        }
                    }
                }
                if (przedm < 0)
                    l_plec++;
            }
        }

    }
    else
        l_plec = 0;
    if (l_plec)
        printf("%d\n", l_plec);
    else
        printf("NIE\n");
    return 0;
}