Author |
Message |
11/03/2019 11:43:26
|
ThePopivanov
Joined: 24/09/2015 23:17:41
Messages: 16
Offline
|
Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто сега на 23 поминува а само на 7 паѓа.
This message was edited 1 time. Last update was at 11/03/2019 13:44:09
|
|
|
11/03/2019 13:42:16
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.
Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.
Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.
(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)
|
|
|
11/03/2019 14:39:35
|
BATIR
Joined: 20/06/2015 16:36:50
Messages: 155
Offline
|
Dali pod bitmaski, mislis za site kombinacii da gledame kolku sme potrosile, pri toa da e validno? I da go barame maksimumot?
|
|
|
11/03/2019 14:50:54
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
BATIR wrote:Dali pod bitmaski, mislis za site kombinacii da gledame kolku sme potrosile, pri toa da e validno? I da go barame maksimumot?
Максимум градови во кои може да се направат митинзи - тоа што се бара во задачата.
Инаку, ако не ме разбра, тоа зборував дека "Постојат и други решенија за добивање на делумни поени" - едно е решението што беше напишано горе (greedy), може со bfs и битмаски (бидејќи има и помали тест случаи на кои се оценуваат решенијата), итн.
|
|
|
11/03/2019 23:20:07
|
ThePopivanov
Joined: 24/09/2015 23:17:41
Messages: 16
Offline
|
longhi wrote:
ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.
Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.
Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.
(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)
Ама не разбирам оти не работи моето решение
|
|
|
11/03/2019 23:32:49
|
petarsor
Joined: 15/07/2018 11:58:27
Messages: 87
Offline
|
ThePopivanov wrote:Ама не разбирам оти не работи моето решение
Бидејќи ваквите greedy алгоритми функционираат за некои задачи, а за некои не.
На пример, изврши ја твојата програма на овој пример:
Ќе добиеш одговор 2. Точниот одговор е 3.
|
|
|
13/03/2019 09:06:04
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
longhi wrote:
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].
Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?
|
|
|
13/03/2019 13:17:07
|
despotovski01
Joined: 23/02/2014 14:36:12
Messages: 37
Offline
|
VlatkoSh wrote:
longhi wrote:
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].
Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?
Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека би било подобро прво да одиме во градот 2, па во градот 1. Тоа е подобро ако и само ако не можеме да одиме прво во 1, па потоа во 2. Според тоа, би важеле следниве неравенства:
P1 > R1, дадено во задачата
P2 > R2, дадено во задачата
R1 > R2, наша претпоставка
N >= P2, за да можеме да појдеме прво во градот 2
N - P1 + R1 < P2, претпоставуваме дека не можеме да појдеме прво во градот 1, па во градот 2. Го обележуваме ова неравенство со (1)
N - P2 + R2 >= P1, претпоставуваме дека можеме да појдеме прво во градот 2, па во градот 1. Го обележуваме ова неравенство со (2)
N < P2 + P1 - R1, добиено од неравенството (1)
N >= P1 + P2 - R2, добиено од неравенството (2)
Бидејќи R1 > R2, P1 + P2 - R1 < P1 + P2 - R2. Тоа ги прави неравенствата (1) и (2) контрадикторни и не може истовремено да важат. Според тоа, заклучуваме дека никогаш не е подобро да одиме прво во градот 2, па во градот 1, а со тоа, сортирањето по R го дава оптималното DP решение.
Дополнително: види го контра-примеров зошто не може да сортираме по P:
This message was edited 1 time. Last update was at 13/03/2019 13:20:20
|
|
|
14/03/2019 09:38:04
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
despotovski01 wrote:
Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека ...
Fala za objasnuvanjeto, nema podobro od dokaz!
|
|
|
|