Задачи за тренинг
Задача 7а. [8.2.1, стр.459]
В един склад имало n вида стоки в ограничени количества. За
всяка стока се знае: цената ci и теглото wi
на една продуктова единица. Задачата е да натовари камион с дадена
товароносимост m със стоки от склада с най-голяма възможна
цена. Обемът на стоките може да бъде пренебрегнат.
Вход:
На входа най-напред се задават числата n и m
- видове стоки и товароносимостта на камиона. На следващите n
реда са дадени брой продуктови единици, тегло wi и
стойност ci на една продуктова единица от
съответния вид стока. Всички числа са цели в интервала [1, 100].
Входът съдържа много примери.
.
Изход:
Отпечатва се максималната стойност за натоварените на камиона стоки
- за всеки пример на отделен ред.
Пример:
3 10
4 1 10
3 4 20
2 5 30
Решение на примера:
70
Пояснение на примера: В склада има 3 вида стоки (n =
3), а товароносимостта на камиона е 10 (m = 10). От първия
вид стока в склада има 4 продуктови единици, всяка с тегло 1 (w1
= 1) и стойност 10 (c1 = 10), от
втория вид - 3 продуктови единици с тегло 4 (w2
= 4) и стойност 20 (c2 = 20) и от
третия вид - 2 продуктови единици с тегло 5 (w3
= 5) и стойност 30 (c3 = 30).
Оптималното решение се получава от 4 продуктови единици от първия
вид стока и една от третия вид, общо тегло 4х1 + 1х5 = 9 и стойност
4х10 + 1х30 = 70.
Задача
7b. Зайче
в беда
Веднъж
малкото
бяло
зайче,
гонено от един ловец попаднало в лабиринт, които имал форма на
квадратна дъска N x N. В него чакал големия лош
вълк, които предварително изкопал дупки, където зайчето да падне
и той да го хване по-лесно. В последния момент зайчето с ужас
разбрало, че може да се движи само в посока надолу и надясно и
че изхода от лабиринта е чак в долния десен ъгъл на дъската.
Зайчето
трябвало
да
разбере
каква е вероятността да излезе от лабиринта без да падне в някоя
дупка. За целта трябвало да изчисли броя пътища от входа до
изхода на лабиринта, като успяло да се снабди с картата на този
лабиринт. Картата е зададена с размер N, като местата на
дупките са означени с 0, а проходимите места с 1. Напишете
програма, която пресмята търсения брой
пътища.
Вход:
На входа се задава числото N
< 100 - размерът на
дъската и матрица с единици и нули. Входът съдържа много примери.
Изход:
За всеки пример на отделен ред се отпечатва цяло число - търсения брой пътища.
Пример:
2
1 1
1 1
3
1 0 1
1 0 1
1 1 1
2
0 1
1 1
Решение на
примера:
2
1
0