Класическа задача за раницата:
    Дадена е раница с вместимост 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/

Задача, дадена на Шести междууниверситетски турнир по програмиране - Шумен, 10 май 2003 г.

Задача F.  Зайче в беда

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

Пример.
 

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