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

Имеются m предметов с номерами от 0 до m -1, для каждого из которых известна масса в килограммах p_j и стоимость c_j (j = 0,1,…, m -1). Определить, какие предметы необходимо положить в рюкзак, чтобы их общая масса не превышала P кг, а общая стоимость была максимальной.
Сколько предметов каждого типа он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной при ограничении на массу рюкзака?

Жадный алгоритм для задачи о рюкзаке состоит в следующем:
Выбрать максимально дорогой предмет, стоимости C_max. Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно дорогими» предметами, пока они влезают. Пусть стоимость этого решения C_greedy В зависимости от того, что больше, C_max или C_greedy, выбрать первое или второе решение.Задача укладки рюкзака сложна. Если перебирать всевозможные подмножества данного набора из k предметов, то получится решение сложности не менее чем O (2^k). Мы рассмотрим решение данной задачи для случая, когда все входные данные - целочисленные, сложность которого будет O (kW). Рассмотрим следующую функцию. Пусть R(s, n) есть максимальная стоимость предметов, которые можно уложить в рюкзак максимальной вместимости n, если можно использовать только первые s предметов из заданных k. Зададим краевые значения функции R(s, n). Если s = 0, то R(0, n) = 0 для всех n (ни один предмет нельзя брать, поэтому максимальная стоимость равна 0). Если n = 0, то R(s, 0) = 0 для всех s (можно брать любые из первых s предметов, но вместимость рюкзака равна 0).

Cоставим рекуррентное соотношение: необходимо из предметов с номерами 1,..., s составить рюкзак максимальной стоимости, чей вес не превышает n. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером s и когда предмет s не попал в максимальный рюкзак. Если предмет s не попал в максимальный рюкзак массы n, то максимальный рюкзак будет составлен только из предметов с номерами 1,..., s - 1, следовательно, A (s, n) = A (s - 1, n). Если же в максимальный рюкзак включен предмет s, то масса оставшихся предметов не превышает n - w _s, а от добавления предмета s общая стоимость рюкзака увеличивается на p _s. Значит, A (s, n) = A (s - 1, n - w _s) + p _s. Теперь из двух возможных вариантов составить рюкзак массы <= n, из предметов 1,..., s нужно выбрать:

A (s, n) = max (A (s - 1, n),
A (s - 1, n - w _s) + p _s.

Ханойские башни

Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.
Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.
При перемещении никогда нельзя класть больший диск на меньший.

void Move(int n, char x,y,z);
//х - А y - В z - C
{ if (n==1) scanf(“ диск 1 %d -> %d“,x,y);
else
if (n>1)
{
Move(n-1,x,z,y);
printf(“диск %2d %d ->%d”,n,x,y);
Move(n-1,z,y,x);
}

Метод быстрой сортировки Хоара

Метод быстрой сортировки массива разрботан в 1962 году профессором Оксфордского университета К. Хоаром. Алгоритм состоит в том, чтобы, выбрав некоторый элемент разделяющим, переместить все элементы меньшие (или равные) его левее, а большие – правее. После этого применить тот же ход для левой части и правой части массива, если в этой части больше одного элемента. Алгоритм – рекурсивный, т.е. соответствующая процедура обращается при реализации к самой себе. Сложность алгоритма – O(n*logn) – в среднем. В худшем случае (когда после разделения на каждом шаге один из подмассивов состоит из одного элемента, а второй – из оставшихся) сложность O(n²)

void qsort(int a[], int l, int r)
{
int i = l, j = r, p;
int x = a[(l + r)/2];
while (i <= j)
{

while (a[i] < x)
++i;
while (x < a[j])

--j;

if (i <= j)
{ p = a[i]; a[i] = a[j]; a[j] = p; i++; j--; }

}
if (l < j)
qsort(a, l, j);
if (i < r)
qsort(a, i, r);

}

Рекурсивные функции сортировки

Упорядочить элементы последовательности A=(ai), i=1..n, используя рекурсивную функцию сортировки.
void rec_sort(int *a, int i, int n) // рекурсивной функция сортировки вставками
{ if (i < n)
{ int max_el = a[i], max_ind = i;
for (int j = i; j < n; ++j)
if (a[j] > max_el)
{ max_el = a[j]; max_ind = j;}

if (max_ind > i)
{ a[i] ^= a[max_ind]; a[max_ind] ^= a[i]; a[i] ^= a[max_ind];}
rec_sort(a, i+1, n);
}}

Решение комбинаторных задач: генерация k-элементных подмножеств, генерация перестановок

Генерация k-элементных подмножеств
В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают C_n^k , при программировании гораздо удобнее использовать следующие рекуррентные соотношения

Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что ранее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать.

19.16.1#include <stdlib.h>
#include <stdio.h>

void genercmn(int n,int m)

{ int i,j;
int *v;
v=(int*)malloc((m+1)*sizeof(int));
int b;
int count=0;
for(i=1;i<=m;i++)
v[i]=i;

do
{
for (;v[m]<=n;v[m]++)
{ // увеличение последнего элемента
for (j=1;j<=m;j++)
printf("%d ",v[j]);
printf("\n");
count++;
}

b=0;
for (i=m-1;i>0;i--)
if(v[i]+1 <=n-(m-i))
{ b=1; break; }
else b=0;
v[i]++;

for (j=i+1;j<=m;j++)
v[j]=v[j-1]+1;
} while (b);
printf ("Count=%d\n",count);
}
void main ()
{
genercmn(3,2);
}

19.16.2#include <stdlib.h>
#include <stdio.h>
int a[100];
int n, m;
// генерация рекурсия
void print(int n)
{
for (int i = 1; i<= n; i++)
{
printf("%d ",a[i]);
}
printf("\n");

void gen(int j, int k)
{ int i;
if (j==0)
{
print (m);
return;
}
for (i = k; i <=n - j + 1; i++)
{
a[m-j+1] = i;
gen (j - 1, i + 1);}}

void cnm(int n, int m)
{
gen(m,1);
}
void main()
{
n=5, m=2;
//a=(int*)malloc((m)*sizeof(int));
for (int i = 0; i <=n; i++)
a[i] = i;
cnm(n,m);
}

19.16.3void print(const *a,int n)

//Генерация k-элементных подмножеств.Генерация сочетаний из n цифр по m. Рекурсивное решение:

{

for (int i = 0; i< n-1; i++)
printf("%d ",a[i]);
printf("\n"); }

void perm(int *a, int n, int m, int first, int ind)
{
if (ind > m)
{ print (a,n);
return;
}
for (int i = first; i <=n - (m - ind); i++)
{ a[ind - 1] = i;
perm (a, n, m, i + 1, ind + 1);}}

void main()
{

int *a;
int n=3, m=2;
a=(int*)malloc((m)*sizeof(int));
perm(a, n, m, 1, 1);
}

Генерация всех перестановок n -элементного множества

void Perm(int i)
{
int j,k;
if (i==n)
{
for (j = 1; j <=n; j++)
printf("%d ",a[p[j]]);
printf ("\n");
}

else
{
for(j=i+1;j<=n; j++)
{ Perm(i+1);
k=p[i]; p[i]=p[j]; p[j]=k;
}
Perm(i+1);

k=p[i];
for(j=i;j<=n-1; j++)
{ p[j]=p[j+1]; p[n]=k; }
}
}

void main()
{
n=3;
//a=(int*)malloc((n)*sizeof(int));
for (int i = 0; i <=n; i++)
a[i]=p[i] = i;
Perm (n);
}

Дата добавления: 2015-10-29