Решение задачи о ранце

[Robb]

Помогите пожалуйста в реализации одномерной задачи о ранце. Желательно на c++. Сам уже из сил выбился. Может есть у кого готовая?

[cNoNim]

Что за задача о ранце?

[liness]

Сообщение от Robb

Помогите пожалуйста в реализации одномерной задачи о ранце. Желательно на c++. Сам уже из сил выбился. Может есть у кого готовая?

молодец чувак...о ранце все знают задачу..

[The_God]

и мне дайте решение задачи 4.1 если у кого есть

[[nuso2f]]

Если это то, о чем я думаю, то программа будет выглядить примерно следующим образом:

/* main.c */
#include <stdio.h>

#define NN 100
#define T 30 // Weight

#define TRY_NEXT() goto __try_block__
#define DUMMY 1
#define FINALLY() goto __finally_block__

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 ();
}
}
}
}
}

if (DUMMY)
{
FINALLY ();
}

__finally_block__ :
{
printf ("%d\n", zm);
}
}

[Nvetal]

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

По-моему в Банди хорошо разобрана. Щас точные реквизиты книги правда не назову.

З.Ы.

Политех, третий курс, ИС?-)

[[nuso2f]]

fixed.

[Robb]

[nuso2f], Спасибо. не понятно, где идёт сравнивание оценок и ветвление

[Robb]

Есть целевая функция:
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]

И пример задачи в двух прикреплённых файлах

[[nuso2f]]

код проецирует условие:

Из заданных n елементов выбрать такие, чтобы суммарный их вес был менее заданного, а стоимость/полезность наибольшей.

Т - заданный вес
A:n, B:n - массивы(вес и стоимость), максимальный размер выбран статически (100), однако выделить память можно уже динамическим методом, после ввода количества элементов.

[[nuso2f]]

код сишный (не ++), в некоторых случаях goto использовать вполне целесообразно.

посмотри исходник всем известной библиотеки GLib, GObject (как часть GLib). Пример тому лексический анализатор GScanner.

[Robb]

Есть ещё у кого варианты? Может есть кто с политехе, кто у мужика с Северного это заказывал?

[Nvetal]

Ну.... Кто заказывал у мужика с северного, те за красивые глаза не отдадут-)

[Robb]

Nvetal, да это уже мои проблемы за что брать. Контакты этих людей есть?