2014B A Q4 - Dynamic Programming
Forum » Discussions / Q&A, Spring 2020 » 2014B A Q4 - Dynamic Programming
Started by: Omri Berkovitch Omri Berkovitch
Date: 14 Jul 2020 16:07
Number of posts: 2
rss icon RSS: New posts
2014B A Q4 - Dynamic Programming
Omri Berkovitch Omri Berkovitch 14 Jul 2020 16:07

I didnt manage to succeed solving the question.
there is a solution by a student that I have found but it looks like it's a recursive solution rather than DP solution
In his solution, he states that -
C[(index),k1(size group 1),(size group 2),m1(sum group 1),m2(sum group 2)] =
C[(index)-1,(size group 1),(size group 2),(sum group 1),(sum group 2)] V
C[(index-1),(size group 1)-1,(size group 2),(sum group 1)-1,(sum group 2)] V
C[(index-1),(size group 1),(size group 2)-1,(sum group 1),(sum group 2)-1]

V is binary or.

trying to simulate this solution there are many overlapping problems computed again and again, so it seems just like a recursive solution.
Did I made something wrong with my simulation, if not I would like to get help to define the right solution to this problem.

Thanks.

by Omri Berkovitch Omri Berkovitch , 14 Jul 2020 16:07
Re: 2014B A Q4 - Dynamic Programming
tal_yank tal_yank 16 Jul 2020 14:19

היי,
אפשר להגדיר תת-בעיה עם ערך בוליאני.
נשים לב שלכל x_i יש לנו 3 אפשרויות: או שהוא ב-I, או שהוא ב-J, או שהוא לא באף אחת מהן. כדאי לחשוב איך הבעיה משתנה בהתאם לכל אפשרות (כלומר מה תת-הבעיה שמתאימה לכל אפשרות).
טל

by tal_yank tal_yank , 16 Jul 2020 14:19
/forum/t-13547424/2014b-a-q4-dynamic-programming#post-
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License
Click here to edit contents of this page.
Click here to toggle editing of individual sections of the page (if possible). Watch headings for an "edit" link when available.
Append content without editing the whole page source.
Check out how this page has evolved in the past.
If you want to discuss contents of this page - this is the easiest way to do it.
View and manage file attachments for this page.
A few useful tools to manage this Site.
Change the name (also URL address, possibly the category) of the page.
View wiki source for this page without editing.
View/set parent page (used for creating breadcrumbs and structured layout).
Notify administrators if there is objectionable content in this page.
Something does not work as expected? Find out what you can do.
General Wikidot.com documentation and help section.
Wikidot.com Terms of Service - what you can, what you should not etc.
Wikidot.com Privacy Policy.

AltStyle によって変換されたページ (->オリジナル) /