Несколько ограничительная задача о ранце

Рюкзак с несколькими ограничениями - это проблема упаковки. Прочитать. http://en.wikipedia.org/wiki/Packing_problem

Хорошим примером может служить следующая задача:

Дан неориентированный граф G, имеющий положительные веса и N вершин.

Вы начинаете с суммы M денег. Чтобы пройти через вершину i, необходимо заплатить S [i] денег. Если денег не хватает - через эту вершину не пройти. Найдите кратчайший путь от вершины 1 до вершины N, соблюдая указанные выше условия; или заявите, что такого пути не существует. Если существует несколько путей одинаковой длины, вывести самый дешевый. Ограничения: 1

Псевдокод:

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
   If (l-S[p]>=0 AND
    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
   i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.