int main (int argc, char *argv[])
{
int i, s, z, zm, N, A[NN], B[NN], P[NN];
scanf ("%d", &N);
for (i = 0; i < N; i++)
{
scanf ("%d %d", &A[i], &B[i]);
}
s = z = zm = 0;
i = -1;
__try_block__ :
{
for (i = ++i; i < N; i++)
{
if (s + A[i] >= T)
{
P[i] = 1;
}
else
{
s += A[i];
z += B[i]; P[i] = 0;
}
if (zm < z)
{
zm = z;
}
for (i = N - 2; i >= 0; i--)
{
if (P[i + 1] == 0)
{
s -= A[i + 1];
z -= B[i + 1];
}
else
{
if (P[i] == 0)
{
s -= A[i]; z -= B[i]; P[i] = 1;
TRY_NEXT ();
}
}
}
}
}
Задача о ранце - классическая задача оптимизации.Суть состоит в том, что у нас есть некоторый сосуд определенного объема и вещи. Вещи характеризуются занимаемой площадью и полезностью. Задача состоит в том, чтобы уложить в ранец как можно более полезный набор вещей.
По-моему в Банди хорошо разобрана. Щас точные реквизиты книги правда не назову.
[nuso2f], Спасибо. не понятно, где идёт сравнивание оценок и ветвление
[Ответ]
Robb 15:52 25.11.2007
Есть целевая функция:
n
∑cjxj->max (1)
J=1
И одно ограничение:
n
∑ajxj<=b (2)
J=1
xi ?{0,1}, i=1…n (3)
Для получения верхних оценок в корне и в следующих вершинах будем использовать теорему Данцига, относящуюся к следующей задаче линейного программирования:
n
∑cjxj->max (4)
J=1
n
∑ajxj<=b
J=1
0<=xj <=1, j=1…n
Эта задача называется непрерывной задачей о ранце.
Задача приведённая, если:
1) cj , aj =1, n и b – целые положительные числа
2) отношения cj /aj yt возрастают по мере возрастания индекса i:
(cj /aj)>=( cj+1 /aj+1), j=1…n-1 (5)
Очевидно, что для любой задачи о ранце существует эквивалентная ей приведённая задача. Сформулируем теорему Данцига.
Оптимальное решение непрерывной приведённой задачи (4)-(5) определяется с помощью следующих рекуррентных соотношений:
**************j-1
******min(aj;b-∑ ai xni)
*************i=1
xnj = _______________
**************aj
0
∑ ai xni =0
i=1
Теорема Данцига позволяет использовать приведённую задачу в качестве релаксации для исходной задачи (1-3). Целая часть максимального значения критерия оптимальности приведённой задачи является верхней оценкой максимально значения критерия в задаче (1-3): V(t)=[F(xn)]. Отметим также, что изложенный в теореме Данцига алгоритм конструирует решение x, в котором значение всех неизвестных, кроме, быть может, одного, является булевым (0 или 1). Заменив нецелочисленную координату решения нулём, получаем допустимое для задачи (1-3) решение xц, где:
xjц= (xjц, если xjц – целое число, 0, если xjц – нецелое число)
Это даёт возможность вычислить нижнею оценку оптимального значения критерия для рассматриваемой задачи: H(t)= F(xц). Если осталась неотброшенной одна вершина, в которой верхняя и нижняя оценки совпадают, то решение xц является для рассматриваемой задачи оптимальным решением. Если же оценки не совпадают, то в векторе x имеется нецелочисленная координата xi , 0<xni<1, в направлении которой и реализуется ветвление по следующему принципу: рассматриваются варианты xni=0 и xni=1; первый из них порождает задачу (1-3) с опушенной переменной xi (в суммах (1) и (3) отсутствуют слагаемые cixi и ai xi соответственно); второй вариант также порождает задачу с опущенной переменной xi, но, кроме того, в критерии (1) добавлена константа ci, а в ограничении (2) b надо заменить на (b-ai).
По обеим ветвям (xni=0 и xni=1) получаем подзадачи, по-прежнему являющиеся задачами о ранце. Таким образом, для дальнейших ветвлений может использоваться всё та же теорема Данцига.
Вершина с нижней и верхней оценками (wk, vk) считается неперспективной и отбрасывается из дальнейшего рассмотрения, если имеется какая либо другая вершина с верхней и нижней оценками (w1, v1) такими, что v1>wk
[Ответ]
Robb 16:04 25.11.2007
И пример задачи в двух прикреплённых файлах
Изображения
Из заданных n елементов выбрать такие, чтобы суммарный их вес был менее заданного, а стоимость/полезность наибольшей.
Т - заданный вес
A:n, B:n - массивы(вес и стоимость), максимальный размер выбран статически (100), однако выделить память можно уже динамическим методом, после ввода количества элементов.
[Ответ]
[nuso2f] 18:11 25.11.2007
код сишный (не ++), в некоторых случаях goto использовать вполне целесообразно.
посмотри исходник всем известной библиотеки GLib, GObject (как часть GLib). Пример тому лексический анализатор GScanner.
[Ответ]
Robb 08:00 27.11.2007
Есть ещё у кого варианты? Может есть кто с политехе, кто у мужика с Северного это заказывал?
[Ответ]
Nvetal 08:07 27.11.2007
Ну.... Кто заказывал у мужика с северного, те за красивые глаза не отдадут-)
[Ответ]
Robb 12:21 27.11.2007
Nvetal, да это уже мои проблемы за что брать. Контакты этих людей есть?
[Ответ]
