Author |
Message |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 30/03/2012 18:35:07
|
mprelevic
Joined: 05/03/2011 00:07:30
Messages: 9
Offline
|
Можи малку помош околу решението на задачава?
Еве го кодот што го напишав:
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 30/03/2012 19:13:31
|
filip_bujaroski
![[Avatar]](/jforum/images/avatar/0f28b5d49b3020afeecd95b4009adf4c.jpg)
Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline
|
Zatoa shto ova e greedy i nema da raboti
eve ti primer na koj kje padne
6
10000000 10 10 10 1 1
|
Live to play, die for fun. |
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 30/03/2012 21:20:48
|
Vikjan94
Joined: 22/02/2011 20:11:00
Messages: 27
Offline
|
Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 03:00:13
|
obi1kenobi
Joined: 18/02/2010 20:01:33
Messages: 168
Offline
|
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 10:56:44
|
Vikjan94
Joined: 22/02/2011 20:11:00
Messages: 27
Offline
|
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 11:04:07
|
tStojkovski
Joined: 13/02/2010 14:23:00
Messages: 108
Location: Гостивар
Offline
|
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 11:48:10
|
Vikjan94
Joined: 22/02/2011 20:11:00
Messages: 27
Offline
|
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 12:34:10
|
tStojkovski
Joined: 13/02/2010 14:23:00
Messages: 108
Location: Гостивар
Offline
|
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 12:43:38
|
Vikjan94
Joined: 22/02/2011 20:11:00
Messages: 27
Offline
|
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
Да, да, нема потреба од дополнително објаснување
Фала за идејата, немаше да ми текне вака да ја решам
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 13:07:57
|
filip_bujaroski
![[Avatar]](/jforum/images/avatar/0f28b5d49b3020afeecd95b4009adf4c.jpg)
Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline
|
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?
|
Live to play, die for fun. |
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 01/04/2012 13:58:48
|
tStojkovski
Joined: 13/02/2010 14:23:00
Messages: 108
Location: Гостивар
Offline
|
filip_bujaroski wrote:
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto? ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
Не мора цела задача на тацна
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 02/04/2012 00:02:26
|
filip_bujaroski
![[Avatar]](/jforum/images/avatar/0f28b5d49b3020afeecd95b4009adf4c.jpg)
Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline
|
tStojkovski wrote:
filip_bujaroski wrote:
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto? ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
Не мора цела задача на тацна ![](http://mendo.mk/jforum/images/smilies/3b63d1616c5dfcf29f8a7a031aaa7cad.gif)
Epa realno se drugo mi beshe jasno osven kako da znam deka ne sum go zemal 2 pati istiot natprevaruvac
|
Live to play, die for fun. |
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 02/04/2012 10:35:40
|
Vikjan94
Joined: 22/02/2011 20:11:00
Messages: 27
Offline
|
tStojkovski wrote:
filip_bujaroski wrote:
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја! ![](http://mendo.mk/jforum/images/smilies/136dd33cba83140c7ce38db096d05aed.gif)
Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto? ![](http://mendo.mk/jforum/images/smilies/283a16da79f3aa23fe1025c96295f04f.gif)
Не мора цела задача на тацна ![](http://mendo.mk/jforum/images/smilies/3b63d1616c5dfcf29f8a7a031aaa7cad.gif)
Овој пристап ти помина на сите тест-примери???
Јас ја направив и така, функционира на 19/20. Реално, може да се води сметка да не се додава неколку пати истиот човек, ама не може да се води сметка колкава ќе биде разликата помеѓу бројот на луѓе во групите.
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 02/04/2012 11:15:39
|
bedzo
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
|
Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.
Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.
Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...
|
|
![](/jforum/templates/default/images/spacer.gif) |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 02/04/2012 17:13:30
|
filip_bujaroski
![[Avatar]](/jforum/images/avatar/0f28b5d49b3020afeecd95b4009adf4c.jpg)
Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline
|
bedzo wrote:Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.
Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.
Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...
Mene za ovoj slucaj mi teknuva samo bruteforce knapsack... :/
Da baras do kade mozes da stignes, i od tamu da go dodavas noviot chlen, shto najverojatno kje bide so ogromna slozenost
|
Live to play, die for fun. |
|
![](/jforum/templates/default/images/spacer.gif) |
|