программа на С

[Antonio1991]

Всем доброе время суток. Хотелось бы попросить помоч с программой. Сама задача имеет следующий вид: организации нужно нанять переводчиков для перервода с определенного множества языков. Каждый из переводчиков владеет несколькими языками и требует определенную зарплату. Требуется определить, каких переводчиков нанять, чтобы сумма расходов на зарплату была минимальной.
Как это сделать? помогите плиз, срочно надо!

[q_proger]

А пример входных данных есть?
Точнее важны ограничения, сколько максимум может быть переводчиков и языков?

[Antonio1991]

входные данные выбираются самостоятельно. лично я сделал чтение из файла в следующем виде:
6 8 // где 6 - кол-во языков, а 8 - кол-во переводчиков
1 0 1 1 0 0 // 1, если переводчик знает язык, 0 если не знает
1 0 0 0 1 0
0 1 1 1 1 0
0 0 0 0 1 1
1 0 1 0 0 1
0 0 0 0 1 0
1 0 0 1 0 1

ну и в отдельном файле для удобства их 3арплаты
100 200 300 700 350 150 270 900
ну собственно все цифры, знания языков и их количество можно выбирать самому...
а никакой важности максимума нет

[q_proger]

Это я к тому, что если их немного, то можно особо не мудрствовать насчет алгоритма и просто устроить глобальный перебор.

[Antonio1991]

к сожалению там как раз алгоритм и нужен...
не у кого ни каких идей нету??

[q_proger]

// входные данные input и salary
const int L = 6, T = 7;
bool input[T][L] = {
    { 1, 0, 1, 1, 0, 0 },
    { 1, 0, 0, 0, 1, 0 },
    { 0, 1, 1, 1, 1, 0 },
    { 0, 0, 0, 0, 1, 1 },
    { 1, 0, 1, 0, 0, 1 },
    { 0, 0, 0, 0, 1, 0 },
    { 1, 0, 0, 1, 0, 1 }};
int salary[T] =
    { 100, 200, 300, 700, 350, 150, 270 };



bool translators[T] = {0};
bool best_comb[T] = {0};

int payment()
{
    int res = 0;
    bool langs[L] = {0};
    for (int i = 0; i < T; i++) {
        if (translators[i]) {
            for (int j = 0; j < L; j++) {
                if (input[i][j]) langs[j] = true;
            }
            res += salary[i];
        }
    }
    for (int i = 0; i < L; i++) {
        if (!langs[i]) return 0xFFFFFFF;
    }
    return res;
}

int main()
{
    int min_payment = 0xFFFFFFF;
    int n = 1 << T;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < T; j++) {
            translators[j] = (i >> j) % 2;
        }
        int p = payment();
        if (p < min_payment) {
            min_payment = p;
            memcpy(best_comb, translators, sizeof(best_comb));
        }
    }
    cout << "SUM Salary = " << min_payment << "\n";
    for (int i = 0; i < T; i++) {
        if (best_comb[i]) cout << i << " ";
    }
    cout << " - translators\n";

    return 0;
}

Единственное что, когда L и T не будут константами, статические массивы или сделай с запасом или объяви динамически