13. Динамично оптимиране - прости случаи [8]

    Класическа задача за раницата:
    Дадена е раница с вместимост M килограма и N предмета, всеки от които се характеризира с две числа - тегло m_i и стойност c_i. Да се избере такова множество от предмети, чиято сумарна стойност е максимална, а сумата от теглата не надвишава M.

    Дефинираме рекурентна целева функция:

    Методът на динамичното оптимиране изисква последователно пресмятане на стойностите на F(i), като за това пресмятане се използват вече пресметнатите стойности за по-малки i.

// knapsack.c
#include <string.h>
#include <stdio.h>

#define MAXN 30    /* max брой предмети */
#define MAXM 1000  /* max вместимост на раницата */

char set[MAXM][MAXN];
/* ако set[i][j]==1, то на стъпка i (вместимост i) в раницата е предмет j */

unsigned Fn[MAXM]; /* стойност на целевата функция */

/* ПРЕДМЕТИ */
const unsigned m[MAXN] = {0, 30, 15, 50, 10, 20, 40, 5, 65}; /* тегло */
const unsigned c[MAXN] = {0,  5,  3,  9,  1,  2,  7, 1, 12}; /* стойност */

const unsigned M = 70; /* вместимост на раницата */
const unsigned N = 8;  /* брой предмети */

void calculate(void)
{ unsigned maxValue, maxIndex, i, j;
  memset(set,0,sizeof(set)); /* set[i][j] = 0 */

  for (i=1; i<=M; i++)
  { maxValue = maxIndex = 0;
    for (j=1; j<=N; j++)              /* опит с предмета с номер j */
     if (m[j]<=i && !set[i-m[j]][j])
      if (c[j] + Fn[i-m[j]] > maxValue)
    { maxValue = c[j] + Fn[i-m[j]];
      maxIndex = j;
    }
    if (maxIndex>0)                  /* има успешен опит */
    { Fn[i] = maxValue;
      memcpy(set[i],set[i-m[maxIndex]], N);
      set[i][maxIndex] = 1;
    }
    if (Fn[i] < Fn[i-1])
    { Fn[i] = Fn[i-1];
      memcpy(set[i],set[i-1], N);
    }
  }
  printf("No:");
  for (i=1; i<=N; i++)
     if (set[M][i]) printf("%5u", i);
  printf("\n Max value: %u", Fn[M]);
}

int main()
{ calculate();
  return 0;
}
    Да разгледаме примера:
N = 8;
index      0  1  2  3  4  5  6  7  8
m[MAXN] = {0, 3, 7, 6, 1, 2, 4, 5, 5};
c[MAXN] = {0, 5, 3, 9, 1, 1, 2, 5, 2}
M = 7;

Fn[0] = 0;
Fn[1] = max { c[4]+Fn[0] } = 1 /4/
Fn[2] = max { c[5]+Fn[0] } = 1 /5/
Fn[3] = max { c[1]+Fn[0], c[4]+Fn[2], c[5]+Fn[1] } = max{5,3,2} = 5 /1/
Fn[4] = max { c[1]+Fn[1], c[4]+Fn[3], c[6]+Fn[0] } = max{6,6,2} = 6 /1,4/
Fn[5] = max { c[1]+Fn[2], c[5]+Fn[3], c[6]+Fn[1], c[7]+Fn[0], c[8]+Fn[0] } = max{6,6,3,5,2} = 6 /1,5/
Fn[6] = max { c[3]+Fn[0], c[4]+Fn[5], c[5]+Fn[4], c[6]+Fn[2], c[7]+Fn[2], c[8]+Fn[1] } = max{9+0,1+5,1+6,2+1,5+1,2+1} = 9 /3/
Fn[7] = max { c[2]+Fn[0], c[3]+Fn[1], c[4]+Fn[6], c[6]+Fn[5], c[7]+Fn[2], c[8]+Fn[5] } = {5+0,9+1,1+9,2+6,5+1,2+6} = 10 /3,4/

// lsc.c
#include <stdio.h>
#include <string.h>
#define MAXN 100
#define MAX(a,b) (((a)>(b)) ? (a) : (b))

char F[MAXN][MAXN];

const char x[MAXN] = "acbcacbcaba";
const char y[MAXN] = "abacacacababa";
unsigned m,n;
/*
         "acb cacbcaba  "   "a  cbcac bcaba"
         "a bacacacababa"   "abacacacab aba"
solution "a b cac caba  "   "a  c cac b aba"
*/
unsigned lcs_len(void)
{ unsigned i,j;
  for (i=0; i<=m; i++) F[i][0] = 0;
  for (j=0; j<=n; j++) F[0][j] = 0;

  for (i=1; i<=m; i++)
     for (j=1; j<=n; j++)
 if (x[i-1] == y[j-1]) F[i][j]=F[i-1][j-1]+1;
 else F[i][j] = MAX(F[i-1][j], F[i][j-1]);
  return F[m][n];
}

void print(unsigned i, unsigned j)
{ if (i==0 || j==0) return;
  if (x[i-1] == y[j-1])
  {  print(i-1,j-1);
     printf("%c", x[i-1]);
  }
  else if (F[i][j] == F[i-1][j]) print(i-1,j);
  else print(i,j-1);
}

int main()
{ m = strlen(x); n = strlen(y);
  printf("%u\n", lcs_len());
  print(m,n);
  return 0;
}
 

Задача 13a. Зайче в беда

    Веднъж малкото бяло зайче, гонено от един ловец попаднало в горния ляв ъгъл на лабиринт, които имал форма на квадратна дъска N x N. В него чакал големия лош вълк, които предварително изкопал дупки, където зайчето да падне, а той да го хване по-лесно. В последния момент зайчето с ужас разбрало, че може да се движи само в посока надолу и надясно, и че изхода от лабиринта е чак в долния десен ъгъл на дъската.
    Зайчето трябвало да разбере каква е вероятността да излезе от лабиринта без да падне в някоя дупка. За целта трябвало да изчисли броя пътища от входа до изхода на лабиринта, като успяло да се снабди с картата на този лабиринт. Местата на дупките на картата са означени с 0, а проходимите места с 1. Напишете програма F.EXE, която пресмята търсения брой пътища.
    Данните се четат от стандартния вход, където на първия ред е записано цялото число К - броя на тестовите примери, а за всеки тестов пример се дава числото N <= 40;  следват N реда с по N числа, като на всяка клетка съответства по едно число 1 или 0 (проходима клетка или дупка).
    На стандартния изход се извеждат К числа - по едно за всеки тестов пример, показващи броя на пътищата за съответния тестов пример. Всяко едно от числата се извежда на отделен ред.

Пример.

Second International Programming Contest - March 28, 2004, Blagoevgrad, Bulgaria

Задача 13b. Winnie-the-Pooh

One day Winnie-the-Pooh decided to go to his friend Piglet. As his custom he wanted to give a present to Piglet. Because he lived in the forest, Pooh decided to take as much acorns as he could on his way to Piglet. You are asked to help Pooh. Note that the forest is a square (M x M, 3 < M < 101). Pooh's house is the leftmost and uppermost cell, Piglet's house is the rightmost and bottom most cell. The number N means that there are N acorns in the cell, for N = 0, 1, 2, 3, 4. The path begins in cell (1, 1) and ends in cell (M, M). Pooh can go from one cell to another if they have a common side and must arrive at Piglet's house as soon as possible (i.e. visiting exact 2M - 1 cells).

Input
The first line of input contains a single number N - number of tests. The next lines are tests. The first line of each test contains a single number M. Each of the next M lines contains M numbers - the number found on the j-th position on the i-th line represent a cell (i, j).

Output
You should output a single number on a single line for each test - the maximum possible amount of acorns collected by Pooh and given to Piglet.

Допълнителна литература:

[1] Лендерт Амерал, Алгоритми и структури от данни в С++, ИК "Софтех", София,  2001, стр. 340
[2] Емил Келеведжиев, Динамично опримиране, Мусала Софт и Анубис, София 2001.
[3] Робърт Седжуик, Алгоритми на С. Том 1, ИК "Софтех", София, 2002, стр. 229.