Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.04.2010, 11:19   #1
fkorto
Новичок
Джуниор
 
Регистрация: 28.04.2010
Сообщений: 6
По умолчанию C++ на русский язык

Пожалуйста, объясните, как работает этот алгоритм ссылка, а то я C++ не знаю. Вот мой пример. Спасибо

Ниже, в сообщении #4, пояснения

Последний раз редактировалось fkorto; 28.04.2010 в 14:25.
fkorto вне форума Ответить с цитированием
Старый 28.04.2010, 12:28   #2
animalshadow
Пользователь
 
Аватар для animalshadow
 
Регистрация: 30.03.2009
Сообщений: 23
По умолчанию

Эмм по ссылке всё написано и даже довольно подробно описано, так-что нет смысла в copy-paste, а тема вообще не соответствует содержанию.

P.S. Пример вообще из Access...
animalshadow вне форума Ответить с цитированием
Старый 28.04.2010, 12:30   #3
coNsept
Форумчанин
 
Аватар для coNsept
 
Регистрация: 14.12.2009
Сообщений: 716
По умолчанию

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

Рюкзак
Объект
Пустое место



Код:
//---------------------------------------------------------------------------

#include <vcl.h>
#include <windows.h>
#include <stdio.h>
#include <conio.h>

#pragma hdrstop
#pragma argsused

//---------------------------------------------------------------------------

const int MaxObject = 512;

int VectorObject[MaxObject], nObject, Volume, vRest, Temp, i, j;

void pInput();
void pOutput();

void main(void)
{
	while (true)
	{
		clrscr();

		pInput();
		pOutput();

		printf("\n[Enter].Повторить программу\n[Escape].Выход из программы");

		EndMark:

		if (getch() == VK_RETURN)
		{ continue; }
		else if (getch() == VK_ESCAPE)
		{ ExitThread(0); }
		else
		{ MessageBoxA(NULL, "Нажмите правильную кнопку", "Atentie!", MB_OK); _asm { jmp EndMark } }
	}
}

void pInput()
{
	printf("Объём рюкзака: "); scanf("%d", &Volume);

	printf("Количетсов объектов: "); scanf("%d", &nObject);

	printf("\n");

	for (int i = 0; i < nObject; i++)
	{ printf("[%d].Размер объекта: ", i + 1); scanf("%d", &VectorObject[i]); }
}

void pOutput()
{
	for (i = 0; i < nObject - 1; i++)
	{
		for (j = i + 1; j < nObject; j++)
		{
			if (VectorObject[i] < VectorObject[j])
			{
				Temp = VectorObject[i];
				VectorObject[i] = VectorObject[j];
				VectorObject[j] = Temp;
			}
		}
	}

	printf("\nРезультат\n\n");

	vRest = Volume;

	for (i = 0; i < nObject; i++)
	{
		if (VectorObject[i] <= vRest)
		{ vRest -= VectorObject[i]; printf("Объект %d размер %d", i + 1, VectorObject[i]); }

		if (vRest < Volume)
		{ printf(" - оставшиеся объем: %d\n", vRest); }
		else { printf("Рюкзак заполнен: невозможно больше поместить объект\n"); }
	}

}

//---------------------------------------------------------------------------
coNsept вне форума Ответить с цитированием
Старый 28.04.2010, 14:12   #4
fkorto
Новичок
Джуниор
 
Регистрация: 28.04.2010
Сообщений: 6
По умолчанию

animalshadow, я понимаю полностью в чём заключается задача. Об этом подробно написано в Википедии, куда я дал ссылку. Почему я так назвал тему? Название такое потому, что я не понимаю формулу в общем виде. А C++ я не знаю и хотел, чтобы мне пояснили по шагам как алгоритм работает.
coNsept, про метод Greedy ничего не знаю, а по коду что он делает тоже понять не могу. Если бы Вы пояснили, то было бы очень хорошо.

В моём примере (ссылка в первом сообщении) я всё делал без какого-либо математического алгоритма, заполнял решая всё в голове перебором.
Имеются предметы номера i с весом w и стоимостью c:
i w c
1 1 10
2 2 5
3 3 3
4 4 20
5 5 7
Заполнить рюкзак, который может выдержать вес w=10 предметами так, чтобы их стоимость была максимально возможной. Каждый предмет имеется только в единственном экземпляре. Решать перебором, как я это делал в голове нельзя, так как в настоящем примере будет очень много предметов, что будет занимать много времени.

В моём примере я заполнял сначала рюкзак с весом w=1 предметом который который должен был при весе w=1 иметь максимальную стоимость (это ячейка B11). Затем я заполнял рюкзак с весом w=2 (ячейка B12), и так далее до веса рюкзака w=10 (до B20). Далее я уже выбирал из двух предметов, заполняя столбец C10:C20. И так далее по столбцам.
Я не могу правильно понять формулу. Я понимаю так, что следующий максимальный элемент (жёлтый E15 в таблице) равен предыдущему (фиолетовый E14) + элемент с координатами строки "вес рюкзака, для которого мы считаем (w=5) - вес рюкзака на предыдущем шаге (w=4) = 1 (строка для веса рюкзака w=1)" и столбца "столбец элемента, для которого мы считаем (i=4) - 1 = 3 (столбец для трёх элементов i=3)" фиолетовый D11.
Мне кажется, что я не так понял формулу, поэтому и прошу описать мне последовательность выполнения кода. Или же, кто понимает как эта формула работает, описать последовательность действий.

Нашёл ещё видео, на котором это объясняют, но я что-то не пойму:
Цитата:
Наш вес текущий делится на то слагаемое, которое хотим добавить, плюс всё остальное. Максимум для всего остального в таблице.
Это в выводе формулы (начало в 13:30)

Последний раз редактировалось fkorto; 28.04.2010 в 17:38.
fkorto вне форума Ответить с цитированием
Старый 28.04.2010, 16:50   #5
was3110
Форумчанин
 
Аватар для was3110
 
Регистрация: 25.04.2010
Сообщений: 254
По умолчанию

А в каком виде должно быть решение? Программа, язык, на листе Excel?
Порядок решения (для уменьшения вариантов перебора) следующий:
рассчитать для каждого предмета дополнительный параметр (удельная стоимость = с/w) и отсортировать массив предметов по этому параметру по убыванию. До тех пор пока самые выгодные предметы умещаются в рукзак, туда им и дорога. Ну а потом, можно поварьировать последними (как правило максимум получается при полной загрузке всего рюкзака, но может быть и исключение).
помогать студентам - моя вторая профессия
was3110 вне форума Ответить с цитированием
Старый 28.04.2010, 17:19   #6
fkorto
Новичок
Джуниор
 
Регистрация: 28.04.2010
Сообщений: 6
По умолчанию

was3110, решение особой роли не играет, так как мне нужно разобраться с формулой, на которую я дал ссылку. Я делаю в Excel, так как там мне проще. C++ я не знаю. Но мне подойдёт и Delphi. Решение в C++ есть (я дал ссылку сверху), но мне бы его кто-нибудь пояснил.
Про удельную стоимость я знаю, но она помогает при полном переборе, чтобы исключить полный перебор (я думаю смысл понятен). А у меня попытка уменьшения числа итераций с использованием формулы, про которую я и спрашиваю.
fkorto вне форума Ответить с цитированием
Старый 29.04.2010, 15:12   #7
was3110
Форумчанин
 
Аватар для was3110
 
Регистрация: 25.04.2010
Сообщений: 254
По умолчанию

Алгоритм из Википедии переписал на VBA. Массив просматривается в EXCEL. Для тестирования (изменения входных данных) должны быть включены макросы. Качай с сайта (мелкие задачки на VB и VBA). Контакты там же.
помогать студентам - моя вторая профессия
was3110 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Русский язык Sanek_ntsk Общие вопросы C/C++ 9 06.03.2008 16:50
Русский язык Elefanter Свободное общение 14 22.02.2008 16:23
Русский язык [Smarik] Паскаль, Turbo Pascal, PascalABC.NET 7 01.02.2008 22:58
РУССКИЙ ЯЗЫК vicdon Паскаль, Turbo Pascal, PascalABC.NET 3 19.11.2007 14:34
переход на русский язык vicdon Паскаль, Turbo Pascal, PascalABC.NET 2 05.11.2007 18:42