Срочно нужна помощь по алгоритму

[Пантер]

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

[VZ]

Посмотри "задачу о рюкзаке."
есть варианты постановки, и решения...
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

[Пантер]

Походу сделал. Код еще не чистил, так что не смейтесь

Код:

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 - номера строк

[alex12]

А в случае чего - обзаведись сортированным по зарплате списком. Может и в ручную по нему надежней будет. Еще вариант - быстренько написать прогу с этим сортированным списком на QTableWidget с возможностью автоматического подсчета суммы выделенных строк.  Такой полуавтоматический метод может помочь. 

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

[Tonal]

А ещё можно раскидать на всех. Больше зарплата - больщий вычит.

[Пантер]

На всех раскидать не получится. Суммы неизменны. И сортировка не поможет, т.к. нужно найти что-то промежуточное между количеством и сходством. Тоже сначала был соблазн отсортировать и брать наибольшие.

[Вячеслав]

Как уже сказали - кинь в Ексель и надругайся над списком скока надо - там это просто и наглядно ....