Задача о рюкзаке

Задача о рюкзаке - NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена.

Вычислительная задача называется NP-полной (от англ. non-deterministic polynomial – «недетерминированные с полиномиальным временем»), если для неё не существует эффективных алгоритмов решения.

Мне понадобилось научить программу выбирать услуги, оказанные пациентам стоматологической поликлиникой в г. Петрозаводске, для оплаты территориальным фондом ОМС, в пределах указанной максимальной суммы.

Я реализовал довольно быстрый алгоритм, основанный на подборе и сравнении случайных вариантов. Максимальное кол-во предметов (услуг) в этом алгоритме ограничено шестьюдесятью четырьмя.

select_things.h, модифицирован 22/01/2021

#ifndef _SELECT_THINGS_H_INCLUDED
#define _SELECT_THINGS_H_INCLUDED

#include "\works\h\ring.h"

struct BOX_PROPERTIES
{
	// инициализируются в вызывающей функции:
	bool bSelectAll; // выбрать все предметы
	double dMaxSum; // максимальная сумма (например 10000.00)
	double dApproxSum; // достаточная сумма, в процентах (например 99.00)
	double dMaxTime; // ограничение по времени выполнения, мс (например 1000.00)

	// инициализируется в fnSelectThingsForAmount():
	char szTimeStart [12 +1]; // время старта в формате "ЧЧ:ММ:СС.ссс"
	int iStartSequence; // значение инициализации генератора случайных чисел
	int iThingsQty; // общее кол-во предметов
	int iCurrQty; // кол-во предметов для выбора
	double dResult; // результат (-1 или вычисленная сумма)
	int iReasonForTermination; // причина завершения:
	// 0 - достигнуто окончание кода функции
	// 1 - отсутствуют описания предметов в массиве things
	// 2 - отсутствуют предметы с ценой равной или меньшей, чем максимальная сумма
	// 3 - кол-во предметов с допустимой ценой больше 64
	// 4 - выбраны все предметы с допустимой ценой
	// 5 - найден предмет с ценой, равной максимальной сумме
	// 6 - выбраны предметы на сумму, равную максимальной сумме
	// 7 - выбраны предметы на сумму большую, чем достаточная сумма
	// 8 - режим выбора всех предметов
	int iSelectedThingsQty; // кол-во выбранных предметов
	int iIterationsQty; // кол-во итераций
	double dElapsedTime; // прошедшее время, мс
	char szTimeEnd [12 +1]; // время завершения в формате "ЧЧ:ММ:СС.ссс"
};

struct BOX_THING
{
	// инициализируются в вызывающей функции:
	int iMergeId; // идентификатор для слияния
	int iId; // идентификатор предмета (например, индекс товара или услуги в базе)
	double dPrice1; // цена
	double dQty1; // кол-во
	double dSum; // сумма

	// инициализируется в fnSelectThingsForAmount():
	int iNum; // порядковый номер предмета в массиве things
	bool bSelected; // предмет выбран
};

// выбор предметов на сумму
void fnSelectThingsForAmount(BOX_PROPERTIES *s_box_properties,RING *things);

#endif

Структура BOX_PROPERTIES заполняется необходимыми параметрами - указывается максимальная сумма, достаточная сумма в процентах, ограничение по времени выполнения. Список возможных предметов (услуг) передаётся в динамическом массиве things. Функция выбора предметов fnSelectThingsForAmount() в структуре BOX_PROPERTIES возвращает результаты своей работы, список выбранных предметов (услуг) помечается в массиве things.

Ниже текст функции выбора предметов на сумму. Можно пролистать его, чтобы побыстрее добраться до результатов тестовых прогонов.

select_things.cpp, модифицирован 22/01/2021

#include <windows.h>
#include "\works\h\maelstrom.h"
#include "\works\h\ring.h"
#include "\works\h\select_things.h"

// выбор предметов на сумму
void fnSelectThingsForAmount(BOX_PROPERTIES *s_box_properties,RING *things)
{
	SYSTEMTIME lt;
	int iCycle;
	int iCurrQty;
	BOX_THING s_box_thing;
	double dTotalSum;
	BOX_THING thing [64];
	int iCurr;
	unsigned int uiMask0; // 8 bits
	unsigned int uiMask1;
	unsigned int uiMask2;
	unsigned int uiMask3;
	unsigned int uiMask4;
	unsigned int uiMask5;
	unsigned int uiMask6;
	unsigned int uiMask7;
	_LARGE_INTEGER timerF;
	_LARGE_INTEGER timer1;
	unsigned int uiRnd0; // 8 bits
	unsigned int uiRnd1;
	unsigned int uiRnd2;
	unsigned int uiRnd3;
	unsigned int uiRnd4;
	unsigned int uiRnd5;
	unsigned int uiRnd6;
	unsigned int uiRnd7;
	double dTmp;
	unsigned int uiResultMask0; // 8 bits
	unsigned int uiResultMask1;
	unsigned int uiResultMask2;
	unsigned int uiResultMask3;
	unsigned int uiResultMask4;
	unsigned int uiResultMask5;
	unsigned int uiResultMask6;
	unsigned int uiResultMask7;
	_LARGE_INTEGER timer2;
	double dTime;
	bool bFound;

	// частота ядра процессора
	QueryPerformanceFrequency(&timerF);

	QueryPerformanceCounter(&timer1); // начало замера

	// инициализация полей в структуре s_box_properties
	fnGetTimeMs(s_box_properties->szTimeStart); // время старта в формате "ЧЧ:ММ:СС.ссс"
	GetLocalTime(&lt);
	s_box_properties->iStartSequence = lt.wMilliseconds; // значение инициализации генератора случайных чисел
	s_box_properties->iThingsQty = things->fnGetQty(); // общее кол-во предметов
	s_box_properties->iCurrQty = 0; // кол-во предметов для выбора
	s_box_properties->dResult = -1.0; // результат (-1 или вычисленная сумма)
	s_box_properties->iReasonForTermination = 0; // причина завершения
	s_box_properties->iSelectedThingsQty = 0; // кол-во выбранных предметов
	s_box_properties->iIterationsQty = 0; // кол-во итераций
	s_box_properties->dElapsedTime = 0.0; // прошедшее время, мс
	*s_box_properties->szTimeEnd = 0; // время завершения в формате "ЧЧ:ММ:СС.ссс"

	// инициализация генератора случайных чисел от системных часов
	srand(s_box_properties->iStartSequence);

	// проверка наличия описаний товаров в массиве things
	if(things->fnGetQty() == 0)
	{
		s_box_properties->iReasonForTermination = 1;
		// расчёт времени выполнения
		QueryPerformanceCounter(&timer2); // повторный замер
		dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
		s_box_properties->dElapsedTime = dTime;
		fnGetTimeMs(s_box_properties->szTimeEnd);
		return;
	}

	// инициализация полей в массиве things
	for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,iCycle);

		s_box_thing.iNum = iCycle;
		s_box_thing.bSelected = false;

		things->fnReplace((char *) &s_box_thing,iCycle,sizeof(s_box_thing));
	}

	// режим выбора всех предметов
	if(s_box_properties->bSelectAll)
	{
		dTotalSum = 0.0;
		for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
		{
			things->fnPop((char *) &s_box_thing,iCycle);

			dTotalSum += s_box_thing.dSum;
			s_box_thing.bSelected = true;

			things->fnReplace((char *) &s_box_thing,iCycle,sizeof(s_box_thing));
		}
		s_box_properties->iCurrQty = s_box_properties->iThingsQty;
		s_box_properties->dResult = dTotalSum;
		s_box_properties->iReasonForTermination = 8;
		s_box_properties->iSelectedThingsQty = s_box_properties->iThingsQty;

		// расчёт времени выполнения
		QueryPerformanceCounter(&timer2); // повторный замер
		dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
		s_box_properties->dElapsedTime = dTime;
		fnGetTimeMs(s_box_properties->szTimeEnd);
		return;
	}

	// проверка наличия предметов с ценой равной или меньшей, чем максимальная сумма
	iCurrQty = 0;
	for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,iCycle);

		if(s_box_thing.dSum <= s_box_properties->dMaxSum)
			iCurrQty++;
	}
	s_box_properties->iCurrQty = iCurrQty; // сохраняем кол-во предметов для выбора
	if(iCurrQty == 0)
	{
		s_box_properties->iReasonForTermination = 2;
		// расчёт времени выполнения
		QueryPerformanceCounter(&timer2); // повторный замер
		dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
		s_box_properties->dElapsedTime = dTime;
		fnGetTimeMs(s_box_properties->szTimeEnd);
		return;
	}
	if(iCurrQty > 64)
	{
		s_box_properties->iReasonForTermination = 3;
		// расчёт времени выполнения
		QueryPerformanceCounter(&timer2); // повторный замер
		dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
		s_box_properties->dElapsedTime = dTime;
		fnGetTimeMs(s_box_properties->szTimeEnd);
		return;
	}

	// подсчёт общей суммы предметов
	dTotalSum = 0.0;
	for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,iCycle);

		// кроме предметов с суммой большей, чем максимальная сумма
		if(s_box_thing.dSum <= s_box_properties->dMaxSum)
			dTotalSum += s_box_thing.dSum;
	}
	if(dTotalSum <= s_box_properties->dMaxSum)
	{
		for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
		{
			things->fnPop((char *) &s_box_thing,iCycle);

			// кроме предметов с ценой большей, чем максимальная сумма
			if(s_box_thing.dSum <= s_box_properties->dMaxSum)
			{
				s_box_thing.bSelected = true;
				s_box_properties->iSelectedThingsQty++;
				things->fnReplace((char *) &s_box_thing,iCycle,sizeof(s_box_thing));
			}
		}
		s_box_properties->dResult = dTotalSum;
		s_box_properties->iReasonForTermination = 4;
		// расчёт времени выполнения
		QueryPerformanceCounter(&timer2); // повторный замер
		dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
		s_box_properties->dElapsedTime = dTime;
		fnGetTimeMs(s_box_properties->szTimeEnd);
		return;
	}

	// поиск предмета с ценой, равной максимальной сумме
	for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,iCycle);

		if(s_box_thing.dSum == s_box_properties->dMaxSum)
		{
			s_box_thing.bSelected = true;
			things->fnReplace((char *) &s_box_thing,iCycle,sizeof(s_box_thing));
			s_box_properties->dResult = s_box_thing.dSum;
			s_box_properties->iReasonForTermination = 5;
			s_box_properties->iSelectedThingsQty = 1;
			// расчёт времени выполнения
			QueryPerformanceCounter(&timer2); // повторный замер
			dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
			s_box_properties->dElapsedTime = dTime;
			fnGetTimeMs(s_box_properties->szTimeEnd);
			return;
		}
	}

	// *****************************
	// * поиск оптимального выбора *
	// *****************************
	// копирование описаний предметов в массив thing [64]
	iCurr = 0;
	for(iCycle = 0; iCycle < s_box_properties->iThingsQty; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,iCycle);

		// кроме предметов с ценой большей, чем максимальная сумма
		if(s_box_thing.dSum <= s_box_properties->dMaxSum)
		{
			thing [iCurr].iMergeId = s_box_thing.iMergeId;
			thing [iCurr].iId = s_box_thing.iId;
			thing [iCurr].dPrice1 = s_box_thing.dPrice1;
			thing [iCurr].dQty1 = s_box_thing.dQty1;
			thing [iCurr].dSum = s_box_thing.dSum;
			thing [iCurr].iNum = s_box_thing.iNum;
			thing [iCurr].bSelected = s_box_thing.bSelected;
//printf("dPrice [%i] = %.2f\n",thing [iCurr].iNum,thing [iCurr].dPrice);
			iCurr++;
		}
	}

	// инициализация восьми 8-битных масок
	switch(iCurrQty)
	{
		// маска 0, младшая
		case 1: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 1; break;
		case 2: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 3; break;
		case 3: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 7; break;
		case 4: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 15; break;
		case 5: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 31; break;
		case 6: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 63; break;
		case 7: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 127; break;
		case 8: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 0; uiMask0 = 255; break;
		// маска 1
		case 9:  uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 1; uiMask0 = 255; break;
		case 10: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 3; uiMask0 = 255; break;
		case 11: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 7; uiMask0 = 255; break;
		case 12: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 15; uiMask0 = 255; break;
		case 13: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 31; uiMask0 = 255; break;
		case 14: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 63; uiMask0 = 255; break;
		case 15: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 127; uiMask0 = 255; break;
		case 16: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 0; uiMask1 = 255; uiMask0 = 255; break;
		// маска 2
		case 17: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 1; uiMask1 = 255; uiMask0 = 255; break;
		case 18: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 3; uiMask1 = 255; uiMask0 = 255; break;
		case 19: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 7; uiMask1 = 255; uiMask0 = 255; break;
		case 20: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 15; uiMask1 = 255; uiMask0 = 255; break;
		case 21: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 31; uiMask1 = 255; uiMask0 = 255; break;
		case 22: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 63; uiMask1 = 255; uiMask0 = 255; break;
		case 23: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 127; uiMask1 = 255; uiMask0 = 255; break;
		case 24: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 0; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		// маска 3
		case 25: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 1; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 26: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 3; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 27: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 7; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 28: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 15; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 29: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 31; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 30: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 63; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 31: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 127; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 32: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 0; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		// маска 4
		case 33: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 1; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 34: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 3; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 35: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 7; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 36: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 15; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 37: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 31; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 38: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 63; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 39: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 127; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 40: uiMask7 = 0; uiMask6 = 0; uiMask5 = 0; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		// маска 5
		case 41: uiMask7 = 0; uiMask6 = 0; uiMask5 = 1; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 42: uiMask7 = 0; uiMask6 = 0; uiMask5 = 3; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 43: uiMask7 = 0; uiMask6 = 0; uiMask5 = 7; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 44: uiMask7 = 0; uiMask6 = 0; uiMask5 = 15; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 45: uiMask7 = 0; uiMask6 = 0; uiMask5 = 31; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 46: uiMask7 = 0; uiMask6 = 0; uiMask5 = 63; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 47: uiMask7 = 0; uiMask6 = 0; uiMask5 = 127; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 48: uiMask7 = 0; uiMask6 = 0; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		// маска 6
		case 49: uiMask7 = 0; uiMask6 = 1; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 50: uiMask7 = 0; uiMask6 = 3; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 51: uiMask7 = 0; uiMask6 = 7; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 52: uiMask7 = 0; uiMask6 = 15; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 53: uiMask7 = 0; uiMask6 = 31; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 54: uiMask7 = 0; uiMask6 = 63; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 55: uiMask7 = 0; uiMask6 = 127; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 56: uiMask7 = 0; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		// маска 7, старшая
		case 57: uiMask7 = 1; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 58: uiMask7 = 3; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 59: uiMask7 = 7; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 60: uiMask7 = 15; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 61: uiMask7 = 31; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 62: uiMask7 = 63; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 63: uiMask7 = 127; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
		case 64: uiMask7 = 255; uiMask6 = 255; uiMask5 = 255; uiMask4 = 255; uiMask3 = 255; uiMask2 = 255; uiMask1 = 255; uiMask0 = 255; break;
	}
/*
printf("uiMask7 = %08b\n",uiMask7);
printf("uiMask6 = %08b\n",uiMask6);
printf("uiMask5 = %08b\n",uiMask5);
printf("uiMask4 = %08b\n",uiMask4);
printf("uiMask3 = %08b\n",uiMask3);
printf("uiMask2 = %08b\n",uiMask2);
printf("uiMask1 = %08b\n",uiMask1);
printf("uiMask0 = %08b\n",uiMask0);
*/

	while(true)
	{
		s_box_properties->iIterationsQty++;

		uiRnd0 = rand();
		if(uiMask1)
			uiRnd1 = rand();
		if(uiMask2)
			uiRnd2 = rand();
		if(uiMask3)
			uiRnd3 = rand();
		if(uiMask4)
			uiRnd4 = rand();
		if(uiMask5)
			uiRnd5 = rand();
		if(uiMask6)
			uiRnd6 = rand();
		if(uiMask7)
			uiRnd7 = rand();

		dTmp = 0;
		if(uiMask0 & uiRnd0 & 1)
			dTmp += thing [0].dSum;
		if(uiMask0 & uiRnd0 & 2)
			dTmp += thing [1].dSum;
		if(uiMask0 & uiRnd0 & 4)
			dTmp += thing [2].dSum;
		if(uiMask0 & uiRnd0 & 8)
			dTmp += thing [3].dSum;
		if(uiMask0 & uiRnd0 & 16)
			dTmp += thing [4].dSum;
		if(uiMask0 & uiRnd0 & 32)
			dTmp += thing [5].dSum;
		if(uiMask0 & uiRnd0 & 64)
			dTmp += thing [6].dSum;
		if(uiMask0 & uiRnd0 & 128)
			dTmp += thing [7].dSum;

		if(uiMask1 & uiRnd1 & 1)
			dTmp += thing [8].dSum;
		if(uiMask1 & uiRnd1 & 2)
			dTmp += thing [9].dSum;
		if(uiMask1 & uiRnd1 & 4)
			dTmp += thing [10].dSum;
		if(uiMask1 & uiRnd1 & 8)
			dTmp += thing [11].dSum;
		if(uiMask1 & uiRnd1 & 16)
			dTmp += thing [12].dSum;
		if(uiMask1 & uiRnd1 & 32)
			dTmp += thing [13].dSum;
		if(uiMask1 & uiRnd1 & 64)
			dTmp += thing [14].dSum;
		if(uiMask1 & uiRnd1 & 128)
			dTmp += thing [15].dSum;

		if(uiMask2 & uiRnd2 & 1)
			dTmp += thing [16].dSum;
		if(uiMask2 & uiRnd2 & 2)
			dTmp += thing [17].dSum;
		if(uiMask2 & uiRnd2 & 4)
			dTmp += thing [18].dSum;
		if(uiMask2 & uiRnd2 & 8)
			dTmp += thing [19].dSum;
		if(uiMask2 & uiRnd2 & 16)
			dTmp += thing [20].dSum;
		if(uiMask2 & uiRnd2 & 32)
			dTmp += thing [21].dSum;
		if(uiMask2 & uiRnd2 & 64)
			dTmp += thing [22].dSum;
		if(uiMask2 & uiRnd2 & 128)
			dTmp += thing [23].dSum;

		if(uiMask3 & uiRnd3 & 1)
			dTmp += thing [24].dSum;
		if(uiMask3 & uiRnd3 & 2)
			dTmp += thing [25].dSum;
		if(uiMask3 & uiRnd3 & 4)
			dTmp += thing [26].dSum;
		if(uiMask3 & uiRnd3 & 8)
			dTmp += thing [27].dSum;
		if(uiMask3 & uiRnd3 & 16)
			dTmp += thing [28].dSum;
		if(uiMask3 & uiRnd3 & 32)
			dTmp += thing [29].dSum;
		if(uiMask3 & uiRnd3 & 64)
			dTmp += thing [30].dSum;
		if(uiMask3 & uiRnd3 & 128)
			dTmp += thing [31].dSum;

		if(uiMask4 & uiRnd4 & 1)
			dTmp += thing [32].dSum;
		if(uiMask4 & uiRnd4 & 2)
			dTmp += thing [33].dSum;
		if(uiMask4 & uiRnd4 & 4)
			dTmp += thing [34].dSum;
		if(uiMask4 & uiRnd4 & 8)
			dTmp += thing [35].dSum;
		if(uiMask4 & uiRnd4 & 16)
			dTmp += thing [36].dSum;
		if(uiMask4 & uiRnd4 & 32)
			dTmp += thing [37].dSum;
		if(uiMask4 & uiRnd4 & 64)
			dTmp += thing [38].dSum;
		if(uiMask4 & uiRnd4 & 128)
			dTmp += thing [39].dSum;

		if(uiMask5 & uiRnd5 & 1)
			dTmp += thing [40].dSum;
		if(uiMask5 & uiRnd5 & 2)
			dTmp += thing [41].dSum;
		if(uiMask5 & uiRnd5 & 4)
			dTmp += thing [42].dSum;
		if(uiMask5 & uiRnd5 & 8)
			dTmp += thing [43].dSum;
		if(uiMask5 & uiRnd5 & 16)
			dTmp += thing [44].dSum;
		if(uiMask5 & uiRnd5 & 32)
			dTmp += thing [45].dSum;
		if(uiMask5 & uiRnd5 & 64)
			dTmp += thing [46].dSum;
		if(uiMask5 & uiRnd5 & 128)
			dTmp += thing [47].dSum;

		if(uiMask6 & uiRnd6 & 1)
			dTmp += thing [48].dSum;
		if(uiMask6 & uiRnd6 & 2)
			dTmp += thing [49].dSum;
		if(uiMask6 & uiRnd6 & 4)
			dTmp += thing [50].dSum;
		if(uiMask6 & uiRnd6 & 8)
			dTmp += thing [51].dSum;
		if(uiMask6 & uiRnd6 & 16)
			dTmp += thing [52].dSum;
		if(uiMask6 & uiRnd6 & 32)
			dTmp += thing [53].dSum;
		if(uiMask6 & uiRnd6 & 64)
			dTmp += thing [54].dSum;
		if(uiMask6 & uiRnd6 & 128)
			dTmp += thing [55].dSum;

		if(uiMask7 & uiRnd7 & 1)
			dTmp += thing [56].dSum;
		if(uiMask7 & uiRnd7 & 2)
			dTmp += thing [57].dSum;
		if(uiMask7 & uiRnd7 & 4)
			dTmp += thing [58].dSum;
		if(uiMask7 & uiRnd7 & 8)
			dTmp += thing [59].dSum;
		if(uiMask7 & uiRnd7 & 16)
			dTmp += thing [60].dSum;
		if(uiMask7 & uiRnd7 & 32)
			dTmp += thing [61].dSum;
		if(uiMask7 & uiRnd7 & 64)
			dTmp += thing [62].dSum;
		if(uiMask7 & uiRnd7 & 128)
			dTmp += thing [63].dSum;

		if(dTmp <= s_box_properties->dMaxSum)
			if(dTmp > s_box_properties->dResult)
			{
//printf("dTmp = %.2f\n",dTmp);
				s_box_properties->dResult = dTmp;
				uiResultMask0 = uiMask0 & uiRnd0;
				uiResultMask1 = uiMask1 & uiRnd1;
				uiResultMask2 = uiMask2 & uiRnd2;
				uiResultMask3 = uiMask3 & uiRnd3;
				uiResultMask4 = uiMask4 & uiRnd4;
				uiResultMask5 = uiMask5 & uiRnd5;
				uiResultMask6 = uiMask6 & uiRnd6;
				uiResultMask7 = uiMask7 & uiRnd7;
				if(dTmp == s_box_properties->dMaxSum)
				{
					// выбраны предметы на сумму, равную максимальной сумме
					s_box_properties->iReasonForTermination = 6;
					break;
				}
			}

		// контроль времени выполнения
		QueryPerformanceCounter(&timer2); // повторный замер
		dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
		if(dTime > s_box_properties->dMaxTime) // мс
			break;
	}

	if(s_box_properties->iReasonForTermination == 0)
		if(s_box_properties->dResult >= s_box_properties->dMaxSum/100.0*s_box_properties->dApproxSum)
			// выбраны предметы на сумму большую, чем достаточная сумма
			s_box_properties->iReasonForTermination = 7;

	if(uiResultMask0 & 1)
		thing [0].bSelected = true;
	if(uiResultMask0 & 2)
		thing [1].bSelected = true;
	if(uiResultMask0 & 4)
		thing [2].bSelected = true;
	if(uiResultMask0 & 8)
		thing [3].bSelected = true;
	if(uiResultMask0 & 16)
		thing [4].bSelected = true;
	if(uiResultMask0 & 32)
		thing [5].bSelected = true;
	if(uiResultMask0 & 64)
		thing [6].bSelected = true;
	if(uiResultMask0 & 128)
		thing [7].bSelected = true;

	if(uiResultMask1 & 1)
		thing [8].bSelected = true;
	if(uiResultMask1 & 2)
		thing [9].bSelected = true;
	if(uiResultMask1 & 4)
		thing [10].bSelected = true;
	if(uiResultMask1 & 8)
		thing [11].bSelected = true;
	if(uiResultMask1 & 16)
		thing [12].bSelected = true;
	if(uiResultMask1 & 32)
		thing [13].bSelected = true;
	if(uiResultMask1 & 64)
		thing [14].bSelected = true;
	if(uiResultMask1 & 128)
		thing [15].bSelected = true;

	if(uiResultMask2 & 1)
		thing [16].bSelected = true;
	if(uiResultMask2 & 2)
		thing [17].bSelected = true;
	if(uiResultMask2 & 4)
		thing [18].bSelected = true;
	if(uiResultMask2 & 8)
		thing [19].bSelected = true;
	if(uiResultMask2 & 16)
		thing [20].bSelected = true;
	if(uiResultMask2 & 32)
		thing [21].bSelected = true;
	if(uiResultMask2 & 64)
		thing [22].bSelected = true;
	if(uiResultMask2 & 128)
		thing [23].bSelected = true;

	if(uiResultMask3 & 1)
		thing [24].bSelected = true;
	if(uiResultMask3 & 2)
		thing [25].bSelected = true;
	if(uiResultMask3 & 4)
		thing [26].bSelected = true;
	if(uiResultMask3 & 8)
		thing [27].bSelected = true;
	if(uiResultMask3 & 16)
		thing [28].bSelected = true;
	if(uiResultMask3 & 32)
		thing [29].bSelected = true;
	if(uiResultMask3 & 64)
		thing [30].bSelected = true;
	if(uiResultMask3 & 128)
		thing [31].bSelected = true;

	if(uiResultMask4 & 1)
		thing [32].bSelected = true;
	if(uiResultMask4 & 2)
		thing [33].bSelected = true;
	if(uiResultMask4 & 4)
		thing [34].bSelected = true;
	if(uiResultMask4 & 8)
		thing [35].bSelected = true;
	if(uiResultMask4 & 16)
		thing [36].bSelected = true;
	if(uiResultMask4 & 32)
		thing [37].bSelected = true;
	if(uiResultMask4 & 64)
		thing [38].bSelected = true;
	if(uiResultMask4 & 128)
		thing [39].bSelected = true;

	if(uiResultMask5 & 1)
		thing [40].bSelected = true;
	if(uiResultMask5 & 2)
		thing [41].bSelected = true;
	if(uiResultMask5 & 4)
		thing [42].bSelected = true;
	if(uiResultMask5 & 8)
		thing [43].bSelected = true;
	if(uiResultMask5 & 16)
		thing [44].bSelected = true;
	if(uiResultMask5 & 32)
		thing [45].bSelected = true;
	if(uiResultMask5 & 64)
		thing [46].bSelected = true;
	if(uiResultMask5 & 128)
		thing [47].bSelected = true;

	if(uiResultMask6 & 1)
		thing [48].bSelected = true;
	if(uiResultMask6 & 2)
		thing [49].bSelected = true;
	if(uiResultMask6 & 4)
		thing [50].bSelected = true;
	if(uiResultMask6 & 8)
		thing [51].bSelected = true;
	if(uiResultMask6 & 16)
		thing [52].bSelected = true;
	if(uiResultMask6 & 32)
		thing [53].bSelected = true;
	if(uiResultMask6 & 64)
		thing [54].bSelected = true;
	if(uiResultMask6 & 128)
		thing [55].bSelected = true;

	if(uiResultMask7 & 1)
		thing [56].bSelected = true;
	if(uiResultMask7 & 2)
		thing [57].bSelected = true;
	if(uiResultMask7 & 4)
		thing [58].bSelected = true;
	if(uiResultMask7 & 8)
		thing [59].bSelected = true;
	if(uiResultMask7 & 16)
		thing [60].bSelected = true;
	if(uiResultMask7 & 32)
		thing [61].bSelected = true;
	if(uiResultMask7 & 64)
		thing [62].bSelected = true;
	if(uiResultMask7 & 128)
		thing [63].bSelected = true;

	// подсчёт кол-ва выбранных предметов
	for(iCycle = 0; iCycle < iCurr; iCycle++)
		if(thing [iCycle].bSelected)
			s_box_properties->iSelectedThingsQty++;

	// копирование сделанного выбора в массив things
	for(iCycle = 0; iCycle < iCurr; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,thing [iCycle].iNum);
		s_box_thing.bSelected = thing [iCycle].bSelected;
		things->fnReplace((char *) &s_box_thing,thing [iCycle].iNum,sizeof(s_box_thing));
	}

	// выбраны предметы на сумму большую, чем достаточная сумма
	if(s_box_properties->iReasonForTermination == 7)
		// дополнительный выбор в несколько проходов
		while(true)
		{
			bFound = false;
			for(iCycle = 0; iCycle < iCurrQty; iCycle++)
			{
				things->fnPop((char *) &s_box_thing,iCycle);

				if(s_box_thing.bSelected == false)
					if(s_box_properties->dResult+s_box_thing.dSum <= s_box_properties->dMaxSum)
					{
						bFound = true;
						s_box_thing.bSelected = true;
						s_box_properties->dResult += s_box_thing.dSum;
						things->fnReplace((char *) &s_box_thing,iCycle,sizeof(s_box_thing));
					}
			}
			if(! bFound)
				break;
		}

	// расчёт времени выполнения
	QueryPerformanceCounter(&timer2); // повторный замер
	dTime = ((timer2.QuadPart-timer1.QuadPart)/(timerF.QuadPart/100000))/100.0;
	s_box_properties->dElapsedTime = dTime;
	fnGetTimeMs(s_box_properties->szTimeEnd);
}

Ниже текст небольшой программы, использовавшейся для тестирования:

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include "\works\h\maelstrom.h"
#include "\works\h\ring.h"
#include "\works\h\select_things.h"

int main(void)
{
	RING *things;
	BOX_THING s_box_thing;
	BOX_PROPERTIES s_box_properties;
	int iCycle;

	things = new RING("things",1024);

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 10;
	s_box_thing.dPrice1 = 100.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 100.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 11;
	s_box_thing.dPrice1 = 170.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 170.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 12;
	s_box_thing.dPrice1 = 235.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 235.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 13;
	s_box_thing.dPrice1 = 410.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 410.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 14;
	s_box_thing.dPrice1 = 655.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 655.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 15;
	s_box_thing.dPrice1 = 10.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 10.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 21;
	s_box_thing.dPrice1 = 15.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 15.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 22;
	s_box_thing.dPrice1 = 28.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 28.0;
	// несколько одинаковых предметов
	for(iCycle = 0; iCycle < 32; iCycle++)
		things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 23;
	s_box_thing.dPrice1 = 37.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 37.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 24;
	s_box_thing.dPrice1 = 43.0;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 43.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 31;
	s_box_thing.dPrice1 = 1.5;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 1.5;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 32;
	s_box_thing.dPrice1 = 3.2;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 3.2;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 33;
	s_box_thing.dPrice1 = 6.4;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 6.4;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 34;
	s_box_thing.dPrice1 = 8.2;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 8.2;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 35;
	s_box_thing.dPrice1 = 9.9;
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 9.9;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 41;
	s_box_thing.dPrice1 = 7100.0; // больше максимума
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 7100.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_thing.iMergeId = 0;
	s_box_thing.iId = 42;
	s_box_thing.dPrice1 = 9000.0; // больше максимума
	s_box_thing.dQty1 = 1.0;
	s_box_thing.dSum = 9000.0;
	things->fnPush((char *) &s_box_thing,sizeof(s_box_thing));

	s_box_properties.bSelectAll = false;
	s_box_properties.dMaxSum = 1700.0+576.0;
	s_box_properties.dApproxSum = 99.0;
	s_box_properties.dMaxTime = 10.0;

	fnSelectThingsForAmount(&s_box_properties,things);

	printf("things:\n");
	for(iCycle = 0; iCycle < s_box_properties.iThingsQty; iCycle++)
	{
		things->fnPop((char *) &s_box_thing,iCycle);

		printf("iId = %2i, dPrice1 = %7.2f, iNum = %2i, bSelected = %s\n",
			s_box_thing.iId,
			s_box_thing.dPrice1,
			s_box_thing.iNum,
			s_box_thing.bSelected ? "true" : "false");
	}
	printf("s_box_properties.szTimeStart = %s\n",s_box_properties.szTimeStart);
	printf("s_box_properties.iStartSequence = %i\n",s_box_properties.iStartSequence);
	printf("s_box_properties.dMaxSum = %.2f\n",s_box_properties.dMaxSum);
	printf("s_box_properties.dApproxSum = %.2f%%\n",s_box_properties.dApproxSum);
	printf("s_box_properties.dMaxTime = %.2f ms\n",s_box_properties.dMaxTime);
	printf("s_box_properties.iThingsQty = %i\n",s_box_properties.iThingsQty);
	printf("s_box_properties.iCurrQty = %i\n",s_box_properties.iCurrQty);
	printf("s_box_properties.dResult = %.2f\n",s_box_properties.dResult);
	printf("s_box_properties.iReasonForTermination = %i (",s_box_properties.iReasonForTermination);
	switch(s_box_properties.iReasonForTermination)
	{
		case 0: // 0 - достигнуто окончание кода функции
		printf("dostignuto okonchanie koda funkcii)\n");
		break;

		case 1: // 1 - отсутствуют описания предметов в массиве things
		printf("otsutstvuiut opisania predmetov v massive 'things')\n");
		break;

		case 2: // 2 - отсутствуют предметы с ценой равной или меньшей, чем максимальная сумма
		printf("otsutstvuiut predmety s cenoi ravnoi ili menshei, chem maksimalnaia summa)\n");
		break;

		case 3: // 3 - кол-во предметов с допустимой ценой больше 64
		printf("kol-vo predmetov s dopustimoi cenoi bolshe 64)\n");
		break;

		case 4: // 4 - выбраны все предметы с допустимой ценой
		printf("vybrany vse predmety s dopustimoi cenoi)\n");
		break;

		case 5: // 5 - найден предмет с ценой, равной максимальной сумме
		printf("naiden predmet s cenoi, ravnoi maksimalnoi summe)\n");
		break;

		case 6: // 6 - выбраны предметы на сумму, равную максимальной сумме
		printf("vybrany predmety na summu, ravnuiu maksimalnoi summe)\n");
		break;

		case 7: // 7 - выбраны предметы на сумму большую, чем достаточная сумма
		printf("vybrany predmety na summu bolshuiu, chem dostatochnaia summa)\n");
		break;
	}	
	printf("s_box_properties.iSelectedThingsQty = %i\n",s_box_properties.iSelectedThingsQty);
	printf("s_box_properties.iIterationsQty = %i\n",s_box_properties.iIterationsQty);
	printf("s_box_properties.szTimeEnd = %s\n",s_box_properties.szTimeEnd);
	printf("s_box_properties.dElapsedTime = %.2f ms\n",s_box_properties.dElapsedTime);

	delete things;	
	return 0;
}

Результаты тестовых прогонов с выбором из 48 услуг с разными ограничениями по времени

Тестовые прогоны выполнялись на старом, но довольно быстром процессоре "Intel Xeon E3 1230 v2" с частотой 3.3 ГГц.

10 миллисекунд, или сотая доля секунды - это значительное время, позволяющее компьютеру проверить около 20 тысяч вариантов. Поэтому результаты работы за такое время весьма неплохие.

Результат тестового прогона в течение 10 мс:

things:
iId = 10, dPrice1 =  100.00, iNum =  0, bSelected = true
iId = 11, dPrice1 =  170.00, iNum =  1, bSelected = true
iId = 12, dPrice1 =  235.00, iNum =  2, bSelected = true
iId = 13, dPrice1 =  410.00, iNum =  3, bSelected = true
iId = 14, dPrice1 =  655.00, iNum =  4, bSelected = true
iId = 15, dPrice1 =   10.00, iNum =  5, bSelected = false
iId = 21, dPrice1 =   15.00, iNum =  6, bSelected = false
iId = 22, dPrice1 =   28.00, iNum =  7, bSelected = true
iId = 22, dPrice1 =   28.00, iNum =  8, bSelected = false
iId = 22, dPrice1 =   28.00, iNum =  9, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 10, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 11, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 12, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 13, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 14, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 15, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 16, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 17, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 18, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 19, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 20, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 21, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 22, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 23, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 24, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 25, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 26, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 27, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 28, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 29, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 30, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 31, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 32, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 33, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 34, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 35, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 36, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 37, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 38, bSelected = true
iId = 23, dPrice1 =   37.00, iNum = 39, bSelected = true
iId = 24, dPrice1 =   43.00, iNum = 40, bSelected = true
iId = 31, dPrice1 =    1.50, iNum = 41, bSelected = false
iId = 32, dPrice1 =    3.20, iNum = 42, bSelected = true
iId = 33, dPrice1 =    6.40, iNum = 43, bSelected = true
iId = 34, dPrice1 =    8.20, iNum = 44, bSelected = false
iId = 35, dPrice1 =    9.90, iNum = 45, bSelected = false
iId = 41, dPrice1 = 7100.00, iNum = 46, bSelected = false
iId = 42, dPrice1 = 9000.00, iNum = 47, bSelected = false
s_box_properties.szTimeStart = 01:48:05.574
s_box_properties.iStartSequence = 574
s_box_properties.dMaxSum = 2276.00
s_box_properties.dApproxSum = 99.00%
s_box_properties.dMaxTime = 10.00 ms
s_box_properties.iThingsQty = 48
s_box_properties.iCurrQty = 46
s_box_properties.dResult = 2275.60
s_box_properties.iReasonForTermination = 7 (vybrany predmety na summu bolshuiu, chem dostatochnaia summa)
s_box_properties.iSelectedThingsQty = 31
s_box_properties.iIterationsQty = 19970
s_box_properties.szTimeEnd = 01:48:05.584
s_box_properties.dElapsedTime = 10.10 ms

За более чем 19 тысяч итераций функция нашла вариант на сумму 2275 рублей 60 копеек, что лишь на 40 копеек меньше указанного допустимого максимума - 2276 рублей.

Результат тестового прогона в течение 1 мс (успешный):

things:
iId = 10, dPrice1 =  100.00, iNum =  0, bSelected = true
iId = 11, dPrice1 =  170.00, iNum =  1, bSelected = true
iId = 12, dPrice1 =  235.00, iNum =  2, bSelected = true
iId = 13, dPrice1 =  410.00, iNum =  3, bSelected = true
iId = 14, dPrice1 =  655.00, iNum =  4, bSelected = true
iId = 15, dPrice1 =   10.00, iNum =  5, bSelected = true
iId = 21, dPrice1 =   15.00, iNum =  6, bSelected = true
iId = 22, dPrice1 =   28.00, iNum =  7, bSelected = true
iId = 22, dPrice1 =   28.00, iNum =  8, bSelected = true
iId = 22, dPrice1 =   28.00, iNum =  9, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 10, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 11, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 12, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 13, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 14, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 15, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 16, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 17, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 18, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 19, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 20, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 21, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 22, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 23, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 24, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 25, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 26, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 27, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 28, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 29, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 30, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 31, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 32, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 33, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 34, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 35, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 36, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 37, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 38, bSelected = true
iId = 23, dPrice1 =   37.00, iNum = 39, bSelected = true
iId = 24, dPrice1 =   43.00, iNum = 40, bSelected = true
iId = 31, dPrice1 =    1.50, iNum = 41, bSelected = true
iId = 32, dPrice1 =    3.20, iNum = 42, bSelected = true
iId = 33, dPrice1 =    6.40, iNum = 43, bSelected = true
iId = 34, dPrice1 =    8.20, iNum = 44, bSelected = true
iId = 35, dPrice1 =    9.90, iNum = 45, bSelected = true
iId = 41, dPrice1 = 7100.00, iNum = 46, bSelected = false
iId = 42, dPrice1 = 9000.00, iNum = 47, bSelected = false
s_box_properties.szTimeStart = 11:43:37.610
s_box_properties.iStartSequence = 610
s_box_properties.dMaxSum = 2276.00
s_box_properties.dApproxSum = 99.00%
s_box_properties.dMaxTime = 1.00 ms
s_box_properties.iThingsQty = 48
s_box_properties.iCurrQty = 46
s_box_properties.dResult = 2264.20
s_box_properties.iReasonForTermination = 7 (vybrany predmety na summu bolshuiu, chem dostatochnaia summa)
s_box_properties.iSelectedThingsQty = 32
s_box_properties.iIterationsQty = 1649
s_box_properties.szTimeEnd = 11:43:37.611
s_box_properties.dElapsedTime = 1.13 ms

За 1 миллисекунду функция успела выполнить 1649 итераций, найдя вариант на сумму 2264 рубля 20 копеек, всего на 11 рублей 80 копеек меньше допустимого максимума.

Результат немного хуже, чем при выборе в течение 10 мс, но всё-таки приемлемый. Подобный результат получается примерно в 50% случаев на моём компьютере.

Результат тестового прогона в течение 1 мс (провальный):

things:
iId = 10, dPrice1 =  100.00, iNum =  0, bSelected = true
iId = 11, dPrice1 =  170.00, iNum =  1, bSelected = true
iId = 12, dPrice1 =  235.00, iNum =  2, bSelected = true
iId = 13, dPrice1 =  410.00, iNum =  3, bSelected = true
iId = 14, dPrice1 =  655.00, iNum =  4, bSelected = true
iId = 15, dPrice1 =   10.00, iNum =  5, bSelected = true
iId = 21, dPrice1 =   15.00, iNum =  6, bSelected = true
iId = 22, dPrice1 =   28.00, iNum =  7, bSelected = false
iId = 22, dPrice1 =   28.00, iNum =  8, bSelected = false
iId = 22, dPrice1 =   28.00, iNum =  9, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 10, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 11, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 12, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 13, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 14, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 15, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 16, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 17, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 18, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 19, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 20, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 21, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 22, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 23, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 24, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 25, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 26, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 27, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 28, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 29, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 30, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 31, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 32, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 33, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 34, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 35, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 36, bSelected = false
iId = 22, dPrice1 =   28.00, iNum = 37, bSelected = true
iId = 22, dPrice1 =   28.00, iNum = 38, bSelected = false
iId = 23, dPrice1 =   37.00, iNum = 39, bSelected = true
iId = 24, dPrice1 =   43.00, iNum = 40, bSelected = true
iId = 31, dPrice1 =    1.50, iNum = 41, bSelected = false
iId = 32, dPrice1 =    3.20, iNum = 42, bSelected = true
iId = 33, dPrice1 =    6.40, iNum = 43, bSelected = false
iId = 34, dPrice1 =    8.20, iNum = 44, bSelected = true
iId = 35, dPrice1 =    9.90, iNum = 45, bSelected = false
iId = 41, dPrice1 = 7100.00, iNum = 46, bSelected = false
iId = 42, dPrice1 = 9000.00, iNum = 47, bSelected = false
s_box_properties.szTimeStart = 15:32:50.852
s_box_properties.iStartSequence = 852
s_box_properties.dMaxSum = 2276.00
s_box_properties.dApproxSum = 99.00%
s_box_properties.dMaxTime = 1.00 ms
s_box_properties.iThingsQty = 48
s_box_properties.iCurrQty = 46
s_box_properties.dResult = 2246.40
s_box_properties.iReasonForTermination = 0 (dostignuto okonchanie koda funkcii)
s_box_properties.iSelectedThingsQty = 31
s_box_properties.iIterationsQty = 1650
s_box_properties.szTimeEnd = 15:32:50.853
s_box_properties.dElapsedTime = 1.19 ms

В этом примере видно, что наилучший найденный выбор чуть хуже, чем требуемые 99%. Программа выполнила 1650 итераций за 1.19 мс.

В реальных задачах видимо не стоит слишком экономить миллисекунды, либо нужно дать пользователю возможность перерасчёта, пусть балуется в своё удовольствие, властвуя над глупым компьютером.

На главную © Д.С. Кузьмин