Задачи за тренинг

Задача 9а. [8.2.1, стр.459]
Да се направи програма за задачата за раницата с по няколко предмета от всеки вид.

Вход:
На входа се задават: брой видове предмети и капацитета на раницата на първия ред; броят, обемът и стойността на видовете предмети на следващите редове. Всички числа са цели в интервала [1, 100]. Входът съдържа много примери.
.
Изход:

Отпечатва се максимално постигнатата стойност за всеки пример на отделен ред.

Пример:
3 10
4 1 10
3 4 20
1 5 30

Решение на примера:
70

Задача 9b.
Да се напише програма за решаване на задачата Зайче в беда.

Вход:
На входа се задава числото 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