Date: 14 Jul 2020 16:07
Number of posts: 2
rss icon RSS: New posts
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.
היי,
אפשר להגדיר תת-בעיה עם ערך בוליאני.
נשים לב שלכל x_i יש לנו 3 אפשרויות: או שהוא ב-I, או שהוא ב-J, או שהוא לא באף אחת מהן. כדאי לחשוב איך הבעיה משתנה בהתאם לכל אפשרות (כלומר מה תת-הבעיה שמתאימה לכל אפשרות).
טל