Максимален Збир (алгоритми)

This message was edited 1 time. Last update was at 15/12/2018 18:00:15

http://mendo.mk/algoritmi/Task.do?competition=150&id=102

Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата? Тест пример:
Влез:
5 5
2 3 4 5 1
1 1 2 4 3
1 3 1 3 1
4 6 3 4 2
3 3 1 1 2
Точен излез:29
1 1
1 2
1 3
1 4
2 4
3 4
4 4
4 5
5 5
Кориснички излез:29
1 1
1 2
2 2
2 3
2 4
2 5
3 5
4 5
5 5

This message was edited 1 time. Last update was at 16/12/2018 00:22:37

boolTrue wrote:Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата?

Тргни од крајот.

petarsor wrote:

boolTrue wrote:Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата?

Тргни од крајот.

Фала сега работи, меѓутоа нели го правам истото во горниот код?

Сакав да скратам неколку редови код.

boolTrue wrote:Фала сега работи, меѓутоа нели го правам истото во горниот код? Сакав да скратам неколку редови код.

Не баш, разгледуваш една позиција (i, j) а печатиш одлуки за друга (m - j, n-i).

This message was edited 1 time. Last update was at 17/12/2018 20:14:31

petarsor wrote:

boolTrue wrote:Фала сега работи, меѓутоа нели го правам истото во горниот код? Сакав да скратам неколку редови код.

Не баш, разгледуваш една позиција (i, j) а печатиш одлуки за друга (m - j, n-i).

Да, ама ова се случува кога двата елементи имаат исти збир, зошто не и кај вториот алгоритам, бидејќи и таму постојат 2 патишта а во решението е можно да е одбран друг од 2та точни патишта, или постои само 1 точен?