Algorithms Dynamic Programming 03. Dividing Presents 60/100 при вярно решена задача

StilianKushev 2 Точки

Algorithms Dynamic Programming 03. Dividing Presents 60/100 при вярно решена задача

Здравейте, имам проблем с джъджа. Задачата е решена правилно, но просто я реших по различен начин от лектора и output-а ми е различен ~~но пак е верен спрямо условието.~~ Ако може някой да погледне и да каже как да го оправя.

Ето задачата и решението ми.

Благодаря предварително :)

Edit: Ако някой друг е пробвал да я реши по същия начин, както knapsack 0/1, когато гледате дали include е по голямо от exclude aко са равни винаги exclude печели понеже трябва да намерим най-краткото решение.

Мерси на TeodorStefanovPld че ми прочете условието :P.

Линка за решението е ъпдеитнат и дава 100/100.

Тагове:

06/09/2019 02:05:51 Open Courses 06/09/2019 11:40:30

Виж всички отговори

TeodorStefanovPld 1274 Точки

Best Answer

Е ти по-скоро някак си greedy подхождаш май към задачата в 3 сутринта ми е трудно да се изразя правилно.

minimize the difference between the values of the presents received by the two
brothers,

Ей това е ключа помня че и аз доста я въртях тая докато се усетя какво греша.

Но тестовете не са прости. Ти не взимаш някак си най малката разлика а тази която се получи. А тестовете са така направени че очакват вианги най -малката разлика между сумите.

Просто очакват определени отговори а ти не ги даваш, удряш еdge cases заради който се ползва динамичното оптимиране. трябва да се разровя имах някакво 100/100 решение.

06/09/2019 02:30:20

StilianKushev 2 Точки

Ами това ми е грешката, мерси. Но иначе просто я решавам като knapsack 0/1 където weight-а и price-а на всеки елемент ми е самото число а capacity-то ми е тоталната сума разделена на две. Аз така се сетих, но едва ли е най краткото решение :D

06/09/2019 11:19:10

Виж всички отговори