http://mendo.mk/jforum/posts/list/6.page JForum - http://www.jforum.net Денеска изменив нешто сега на 23 поминува а само на 7 паѓа.

[code]#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool sporedba(pair<int, int> par1, pair<int, int> par2) {
return (par1.first-par1.second < par2.first-par2.second);
}

main() {
int N, C, counter = 0;
cin >> N >> C;
vector<pair<int, int> > city;
city.resize(C);
for(int i = 0, a, b; i < C; i++) {
cin >> a >> b;
city[i] = make_pair(a, b);
}
sort(city.begin(), city.end(), sporedba);
for(int i = 0; i < C; i++) {
if(N >= city[i].first) {
counter++;
N-=city[i].first;
N+=city[i].second;
}
}
cout << counter;
return 0;
}
[/code]]]> http://mendo.mk/jforum/posts/preList/687/3749.page http://mendo.mk/jforum/posts/preList/687/3749.page GMT Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.[/quote]

Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.

Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)
[code]#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
int N, C;
cin >> N >> C;

vector<pair<int, int> > cities(C);
for (int i=0; i<C; i++) {
cin >> cities[i].second >> cities[i].first;
}

sort(cities.begin(), cities.end());
reverse(cities.begin(), cities.end());

int dp[C+1][N+1];
memset(dp, 0, sizeof(dp));

int result = 0;

for (int m=0; m<C; m++) {
int cost = cities[m].second, back = cities[m].first;

for (int fromCost=N; fromCost >= 0; fromCost--) {

//da ne se pravi miting vo gradot (m)
dp[m+1][fromCost] = max(dp[m+1][fromCost], dp[m][fromCost]);

//da se pravi miting vo gradot (m)
if (fromCost >= cost) { //mora da imame dovolno sredstva
int toCost = fromCost - cost + back;

dp[m + 1][toCost] = max(dp[m + 1][toCost], dp[m][fromCost] + 1);
result = max(result, dp[m + 1][toCost]);
}
}
}

cout << result;
return 0;
}[/code]]]> http://mendo.mk/jforum/posts/preList/687/3750.page http://mendo.mk/jforum/posts/preList/687/3750.page GMT http://mendo.mk/jforum/posts/preList/687/3751.page http://mendo.mk/jforum/posts/preList/687/3751.page GMT Максимум градови во кои може да се направат митинзи - тоа што се бара во задачата.
Инаку, ако не ме разбра, тоа зборував дека "Постојат и други решенија за добивање на делумни поени" - едно е решението што беше напишано горе (greedy), може со bfs и битмаски (бидејќи има и помали тест случаи на кои се оценуваат решенијата), итн.]]> http://mendo.mk/jforum/posts/preList/687/3752.page http://mendo.mk/jforum/posts/preList/687/3752.page GMT Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.[/quote]

Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.

Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)[/quote]
Ама не разбирам оти не работи моето решение
]]> http://mendo.mk/jforum/posts/preList/687/3755.page http://mendo.mk/jforum/posts/preList/687/3755.page GMT
Бидејќи ваквите greedy алгоритми функционираат за некои задачи, а за некои не.
На пример, изврши ја твојата програма на овој пример:

[code]10 3
10 8
2 1
2 1
[/code]

Ќе добиеш одговор 2. Точниот одговор е 3.]]> http://mendo.mk/jforum/posts/preList/687/3756.page http://mendo.mk/jforum/posts/preList/687/3756.page GMT Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].
[/quote]

Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?]]> http://mendo.mk/jforum/posts/preList/687/3763.page http://mendo.mk/jforum/posts/preList/687/3763.page GMT Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].
[/quote]

Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?[/quote]

Нека 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:
[code]
30 2
25 1
10 5
[/code]]]> http://mendo.mk/jforum/posts/preList/687/3765.page http://mendo.mk/jforum/posts/preList/687/3765.page GMT Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека ...
[/quote]

Fala za objasnuvanjeto, nema podobro od dokaz!]]> http://mendo.mk/jforum/posts/preList/687/3769.page http://mendo.mk/jforum/posts/preList/687/3769.page GMT