Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Пантер от Сентябрь 18, 2007, 16:58



Название: Срочно нужна помощь по алгоритму
Отправлено: Пантер от Сентябрь 18, 2007, 16:58
Заранее извиняюсь, что вопрос не по куте.
Очень нужно на завтра придумать алгоритм, а то придется вручную шерстить список на 300-400 человек. В общем задача такая:
Есть список людей с з/п.
Денег не хватает и нужно убрать людей, сумма з/п которых будет наиболее приближена к недостаче.
Список из 300-400 фамилий.
Величина з/п нестабильна, т.е. варьируется от 0.10 р до 3000 р.


Название: Re: Срочно нужна помощь по алгоритму
Отправлено: VZ от Сентябрь 18, 2007, 19:49
Посмотри "задачу о рюкзаке."
есть варианты постановки, и решения...
http://www.ishodniki.ru/list/info.php?id=7803
http://lib.custis.ru/index.php/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5:%D0%B6%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC



Название: Re: Срочно нужна помощь по алгоритму
Отправлено: Пантер от Сентябрь 18, 2007, 19:59
Походу сделал. Код еще не чистил, так что не смейтесь
Код:
struct People
{
int number;
double money;
};
QStringList MainWindowImpl::findMinSumm (const QList<People> qlstIn, const double dSumm, const double dPogr)
{
static int index=0;
index++;
qlLabel->setText( QString().setNum(index));
QCoreApplication::processEvents();
QList <People> qlstTmp=qlstIn;
QStringList qslReturnList;
while(qlstTmp.count()>0)
{
if (qlstTmp.count()==1)
if ((qlstTmp.at(0).money<=dSumm) && (qlstTmp.at(0).money>=dSumm-dPogr))
{
qslReturnList << QString().setNum(qlstTmp.at(0).number);
qlstTmp.removeAt(0);
continue;
}
People people=qlstTmp.at(0);
qlstTmp.removeAt(0);
QStringList qslTmpList=findMinSumm(qlstTmp,dSumm-people.money,dPogr);
if (qslTmpList.isEmpty()) continue;
for (int j=0; j < qslTmpList.count(); j++)
{
qslReturnList << QString().setNum(people.number)+" "+qslTmpList.at(j);
}
}
qlLabel->setText( QString().setNum(index));
QCoreApplication::processEvents();
return qslReturnList;
}
Выходное значение список строк типа
1 5 10 - номера строк


Название: Re: Срочно нужна помощь по алгоритму
Отправлено: alex12 от Сентябрь 18, 2007, 20:11
А в случае чего - обзаведись сортированным по зарплате списком. ;) Может и в ручную по нему надежней будет. Еще вариант - быстренько написать прогу с этим сортированным списком на QTableWidget с возможностью автоматического подсчета суммы выделенных строк.  Такой полуавтоматический метод может помочь.  ;D

Кстати, прогу можно не писать, а сделать все в Excel'е.


Название: Re: Срочно нужна помощь по алгоритму
Отправлено: Tonal от Сентябрь 18, 2007, 20:14
А ещё можно раскидать на всех. Больше зарплата - больщий вычит.


Название: Re: Срочно нужна помощь по алгоритму
Отправлено: Пантер от Сентябрь 18, 2007, 20:19
На всех раскидать не получится. :( Суммы неизменны. И сортировка не поможет, т.к. нужно найти что-то промежуточное между количеством и сходством. Тоже сначала был соблазн отсортировать и брать наибольшие. :)


Название: Re: Срочно нужна помощь по алгоритму
Отправлено: Вячеслав от Сентябрь 18, 2007, 22:26
Как уже сказали - кинь в Ексель и надругайся над списком скока надо - там это просто и наглядно ....