{"id":2188,"date":"2020-07-29T08:31:36","date_gmt":"2020-07-29T08:31:36","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2188"},"modified":"2022-03-28T01:18:26","modified_gmt":"2022-03-28T01:18:26","slug":"chocolate-dilemma","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/chocolate-dilemma\/","title":{"rendered":"CHOCOLATE DILEMMA"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Dynamic programming<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(SIMPLIFIED):<\/h3>\n
\n

Arnab can take one candy from each row of candies but with the restrictions imposed:<\/p>\n

    \n
  1. There are 3 sections in each row;<\/li>\n
  2. If he takes candy from jth section in the ith row,then in (i+1)th<\/sup> row ,he can’t choose candy from the same section i.e. jth section. <\/li>\n<\/ol>\n<\/blockquote>\n

    <\/strong><\/u><\/a><\/p>\n

    For Example :<\/h4>\n
    6 6 \n1 3 5 2 4 6 \n6 4 5 1 3 2 \n1 3 5 2 4 6 \n6 4 5 1 3 2 \n6 4 5 1 3 2 \n1 3 5 2 4 6\n\nArnab selects sweets \nrow 1: 6\nrow 2: 6\nrow 3: 6\nrow 4: 6\nrow 5: 5\nrow 6: 6\nsum =35<\/code><\/pre>\n
    OBSERVATION:<\/h3>\n
    \n
    To get the maximum sum of sweetness values,he must select sweets with maximum sweetness value from each section keeping in mind the constraints mentioned.<\/p>\n
    Also,you could observe that of all the values of each section ,only the maximum one is relevant.
    \nFor example:<\/p>\n<\/blockquote>\n
    n=3,m=6;\n1 3 5 2 4 6 \n6 4 5 1 3 2 \n1 3 5 2 4 6\n\nFor the first row,The relevant values for each section are:\nsection 1: max(1,3) i.e. 3\nsection 2: max(5,2) i.e. 5\nsection 3: max(4,6) i.e. 6<\/code><\/pre>\n
    SOLVING APPROACH:<\/h3>\n
    \n
    This question has a simple and elegant dynamic programming approach.<\/p>\n
    Let’s define a funtion sweetness_r(i,s) , where i denotes the row which we are currently on and s denotes the section. It is clearly mentioned in the question that we have only 3 sections.Therefore,<\/p>\n
    sweetness_r(i,0)=a[i][0]+max(sweetness_r(i,1),sweetness_r(i,2));<\/strong><\/p>\n
    sweetness_r(i,1)=a[i][1]+max(sweetness_r(i,0),sweetness_r(i,2));<\/strong><\/p>\n
    sweetness_r(i,2)=a[i][0]+max(sweetness_r(i,1),sweetness_r(i,0));<\/strong><\/p>\n
    Then print the maximum of sweetness_r(n,0),sweetness_r(n,1) and sweetness_r(n,2) ,where n is the number of rows.<\/p>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t