Пример выполнения работы. Пусть требуется разработать алгоритм решения задачи о рюкзаке

Пусть требуется разработать алгоритм решения задачи о рюкзаке. Имеется n различных предметов, известны масса каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общая масса не превышала заданной границы, а общая стоимость была максимальна.

Траекторией данной задачи является подмножество выбранных предметов (предметов положенных в рюкзак), функционалом – стоимость данных предметов. Таким образом, для решения задачи необходимо перебрать все 2 ⁿ подмножеств предметов и найти подмножество, удовлетворяющее условиям задачи.

Пусть масса и стоимость предметов хранятся в массиве записей MS. Каждая запись содержит два поля: M – масса предмета и S – стоимость предмета. В переменной n хранится число предметов, в переменной MaxSM – максимальная суммарная масса выбранных предметов.

Текущее подмножество предметов будем хранить в массиве b, в котором b [ i ]=1, если i -й предмет принадлежит подмножеству, и b [ i ]=0, если i -й предмет не принадлежит подмножеству. Суммарную стоимость и массу предметов составляющих текущее подмножество будем хранить в переменных SS и SM соответственно. Для запоминания подмножества выбранных предметов будем использовать массив b 1 аналогичный массиву b. Суммарную стоимость выбранных предметов будем хранить в переменной MaxSS.

Укрупненная блок-схема алгоритма решения задачи представлена на рис.Л4.

Для организации перебора траекторий вначале возьмем алгоритм порождения подмножеств в порядке двоичного счета. Реализация этого варианта алгоритма решения задачи на языке Си будет следующей:

#include <stdio.h>

#include <stdlib.h>

#define maxN 20 //Максимальное число предметов

typedef struct { float M; //Масса предмета

float S; //Стоимость предмета

} t_el_MS;

int n; //Число предметов

t_el_MS MS[maxN]; //Масса и стоимость предметов

int b[maxN+1]; //Текущее подмножество предметов

int b1[maxN]; //Подмножество выбранных предметов

float SM,SS; //Суммарная масса и стоимость предметов,

//составляющих текущее подмножество

float maxSM,maxSS; //Суммарная масса и стоимость выбранных предметов

void Init (int *n, t_el_MS MS[], float *maxSM) {

int i;

printf ("Введите число предметов (не более %d)=",maxN);

scanf ("%d",n);

printf ("Введите массу каждого предмета:\n");

for (i=0;i<*n;i++) { printf ("%d:",i+1); scanf ("%f",&(MS[i].M));}

printf ("Введите стоимость каждого предмета:\n");

for (i=0;i<*n;i++) { printf ("%d:",i+1); scanf ("%f",&(MS[i].S));}

printf ("Введите максимальную суммарную массу выбранных предметов =");

scanf ("%f",maxSM);

}

void Print_rez (int n, int b1[], float maxSM, float maxSS) {

int i;

if (maxSS>0) {

printf ("Суммарная масса предметов со следующими номерами: ");

for (i=0;i<n;i++) { if (b1[i]==1) printf ("%d ",i+1); }

printf ("\n");

printf ("не превышает установленного предела равного %f,", maxSM);

printf ("а суммарная стоимость этих предметов максимальна и равна %f.\n", maxSS);

}

}

void Repl (int b[], int b1[]) {

int i;

for (i=0;i<n;i++) b1[i]=b[i];

}

void Func (int n, t_el_MS MS[], int b[], float *SM, float *SS) {

int i;

*SM=0; *SS=0;

for (i=0;i<n;i++) {

if (b[i]==1) { *SM=*SM+MS[i].M; *SS=*SS+MS[i].S; }

}

}

int i,j;

int main (void) {

setbuf (stdout, NULL);

printf ("ЗАДАЧА О РЮКЗАКЕ\n");

Init(&n,MS,&maxSM);

maxSS=0;

for (i=0;i<=n;i++) b[i]=0;

while (b[n]!=1) {

Func(n,MS,b,&SM,&SS);

if ((SM<=maxSM)&&(SS>maxSS)) { maxSS=SS; Repl(b,b1); }

i=0;

while (b[i]==1) { b[i]=0; i++; }

b[i]=1;

}

Print_rez(n,b1,maxSM,maxSS);

printf ("Работа программы завершена.\n");

return EXIT_SUCCESS;

}

Если при организации перебора траекторий за основу взять алгоритм порождения подмножеств в порядке минимального изменения, то быстродействие алгоритма может быть повышено. Это достигается за счет более быстрого подсчета функционала.

Действительно если подмножества порождаются в порядке минимального изменения, то текущее подмножество отличается от предыдущего только одним элементом. Поэтому для подсчета суммарной стоимости предметов составляющих текущее подмножество (переменная SS) не надо суммировать стоимость каждого из этих предметов. Достаточно выполнить только одно из действий:

- если переход от предыдущего подмножества предметов к текущему подмножеству осуществляется путем удаления некоторого предмета, то необходимо от стоимости предметов составляющих предыдущее подмножество отнять стоимость данного предмета;

- если переход от предыдущего подмножества предметов к текущему подмножеству осуществляется путем добавления некоторого предмета, то необходимо к стоимости предметов составляющих предыдущее подмножество добавить стоимость данного предмета.

Сказанное относится и к подсчету суммарной массы предметов составляющих текущее подмножество (переменная SM).

Реализация такого варианта алгоритма решения задачи на языке Си будет следующей:

#include <stdio.h>

#include <stdlib.h>

#define maxN 20 //Максимальное число предметов

#define maxStack 20 //Максимальный размер стека

typedef struct { float M; //Масса предмета

float S; //Стоимость предмета

} t_el_MS;

typedef struct { int St[maxStack]; //Элементы стека

int t; //Номер вершины стека

} t_S;

int n; //Число предметов

t_el_MS MS[maxN]; //Масса и стоимость предметов

int b[maxN+1]; //Текущее подмножество предметов

int b1[maxN]; //Подмножество выбранных предметов

float SM,SS; //Суммарная масса и стоимость предметов,

//составляющих текущее подмножество

float maxSM,maxSS; //Суммарная масса и стоимость выбранных предметов

t_S St; //Стек

void Init (int *n, t_el_MS MS[], float *maxSM) {

int i;

printf ("Введите число предметов (не более %d)=",maxN);

scanf ("%d",n);

printf ("Введите массу каждого предмета:\n");

for (i=0;i<*n;i++) { printf ("%d:",i+1); scanf ("%f",&(MS[i].M));}

printf ("Введите стоимость каждого предмета:\n");

for (i=0;i<*n;i++) { printf ("%d:",i+1); scanf ("%f",&(MS[i].S));}

printf ("Введите максимальную суммарную массу выбранных предметов =");

scanf ("%f",maxSM);

}

void Print_rez (int n, int b1[], float maxSM, float maxSS) {

int i;

if (maxSS>0) {

printf ("Суммарная масса предметов со следующими номерами: ");

for (i=0;i<n;i++) { if (b1[i]==1) printf ("%d ",i+1); }

printf ("\n");

printf ("не превышает установленного предела равного %f,", maxSM);

printf ("а суммарная стоимость этих предметов максимальна и равна %f.\n", maxSS);

}

}

void Repl (int b[], int b1[]) {

int i;

for (i=0;i<n;i++) b1[i]=b[i];

}

void Func (int n, t_el_MS MS[], int b[], int num, float *SM, float *SS) {

if (b[num]==0) { *SM=*SM-MS[num].M; *SS=*SS-MS[num].S; }

else { *SM=*SM+MS[num].M; *SS=*SS+MS[num].S; }

}

int EmptyStack (t_S *S) { //Проверка стека на пустоту

return S->t==-1?1:0;

}

void PutStack (t_S *S, int el) { //Помещение в стек

S->t=S->t+1;

if ((S->t)>=maxStack) { printf ("Стек переполнен!\n"); exit (1); }

S->St[S->t]=el;

}

void GetStack (t_S *S, int *el) { //Извлечение из стека

if (EmptyStack(S)) { printf ("Стек пуст!\n"); exit (1); }

*el=S->St[S->t];

S->t=S->t-1;

}

void InitStack (t_S *S) { //Инициализация стека

S->t=-1; }

int i,j;

int main (void) {

setbuf (stdout, NULL);

printf ("ЗАДАЧА О РЮКЗАКЕ\n");

Init(&n,MS,&maxSM);

maxSS=0; SM=0; SS=0;

InitStack(&St);

for (i=n-1;i>=0;i--) { b[i]=0; PutStack(&St,i); }

while (!EmptyStack(&St)) {

GetStack(&St,&i);

b[i]=!b[i];

Func(n,MS,b,i,&SM,&SS);

if ((SM<=maxSM)&&(SS>maxSS)) { maxSS=SS; Repl(b,b1); }

for (j=i-1;j>=0;j--) PutStack(&St,j);

}

Print_rez(n,b1,maxSM,maxSS);

printf ("Работа программы завершена.\n");

return EXIT_SUCCESS;

}

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

Контрольные вопросы к защите

Список контрольных вопросов содержит вопросы для повторения темы 2 и 3 а также следующие вопроосы:

1. Понятие задачи выбора.

2. Что характерно для задач выбора?

3. Понятие траектории и функционала.

Дата добавления: 2014-12-27