Билет No12
1. С помощью алгоритма Форда-Беллмана найти кратчайшие расстояния от
вершины 5 (нумерация вершин начинается с 0) до всех остальных вершин
связного взвешенного неориентированного графа, имеющего 6 вершин.
Граф задан матрицей смежности, (0 означает, что соответствующей дуги
нет).
2. Имеется склад, на котором присутствует некоторый ассортимент товаров.
Запас каждого товара неограничен. У каждого товара своя стоимость сi и
масса mi. Методом динамического программирования сформировать такой
набор товаров с максимальной стоимостью, чтобы его суммарная масса не
превышала заданную грузоподъемность М.
Номер товара, i mi сi M
1 4 24
192 2 12
3 5 21