Python-сообщество

Здравствуйте.
Нужно найти алгоритм решения нижеприведенной задачи. Причем алгоритм должен быть НЕ указанный ниже.
Буду рад любым вашим мыслям на этот вопрос
ps. препод принимает только на маткаде :(
Задача.
На входе имеем таблицу:

где 1 столбец: сколько вложено (от 0 до 10 через 1), 2 столбец(I город) - прибыль полученная от этого вложения, 3 и 4 для II и III города соответственно.
Нам нужно найти максимальную прибыль со всех городов при общем вложении 10$, те ответ должен быть примерно таким (5+3+2) = 1,35 . (внутри скобок это распределение по городам и сумма равна 10)
Решение.
1) тупой перебор.
т.е. генерируем все возможные комбинации и считаем с них доход, максимальный и будет наш ответ
(10+0+0)=0,1; (9+0+1)=0,2;……(1+5+4)=0,3

2)как в книге ‘А. Кофман, Р.Фор Займемся исследованием операций.’
https://docs.google.com/document/d/1mNkxrSJ48wrJLf_8YX3Sx6ydblhvePQeLyOTI3aamVE/edit?hl=en

3)Преобразуем матрицу вложений в “дифференциальную” форму - когда в столбцах вложений указаны не абсолютные значения прибыли, а прибыль на очередной “$” вложения
http://xmages.net/storage/10/1/0/a/6/upload/dfd380de.jpg
Вычисляем оптимальные вложения
Ограничения: зависимость “прибыль от числа вложенных $” для ис-ходных зон должна быть НЕУБЫВАЮЩЕЙ функцией.
http://xmages.net/storage/10/1/0/f/7/upload/cc558e01.jpg

Это классическая “Задача о ранце”, где вложение это вес, а сумма прибыли со всех городов - стоимость. Решение — в гугле.