{"id":2057,"date":"2020-07-29T08:32:21","date_gmt":"2020-07-29T08:32:21","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2057"},"modified":"2022-03-30T08:24:08","modified_gmt":"2022-03-30T08:24:08","slug":"foolish-items","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/foolish-items\/","title":{"rendered":"FOOLISH ITEMS"},"content":{"rendered":"

\"\"<\/p>\n

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

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

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

Easy.<\/p>\n<\/blockquote>\n

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

Arnab is now handed N rupees, he is asked by his mom to buy at least two ingredients which when used to make a dish will be sweetest.
\nThe sweetness of the dish is the product of the cost of all the ingredients.
\nNow Arnab’s Mom has given Arnab the exact amount, so after buying the suitable ingredients there will be no money left with Arnab. The market which Arnab visits have ingredients of all possible positive costs (cost>0). Help Arnab find the maximum value of sweetness.<\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
\n

N=4,<\/p>\n

4 can be divided into (1,3)<\/code>and (2,2)<\/code> . (2,2)<\/code> gives the maximum result i.e. 4<\/code>.<\/p>\n

N=5,<\/p>\n

Similarly,we can divide 5 as- (1,4)<\/code> and (2,3)<\/code>. 2*3 gives the maximum product.<\/p>\n<\/blockquote>\n

OBSERVATION:<\/h4>\n
\n

WRONG APPROACH:<\/strong><\/p>\n

One may think that dividing the given number into two equal halves gives the maximum product. But this approach is wrong.<\/p>\n

Example:<\/strong> N=10; if you think (5,5)<\/code> gives the maximum product ,you are wrong because the maximum product is 36!!
\n10 can be divided as [3,3,4]<\/code>.<\/p>\n

Mathematically, we are given n and we need to maximize a1 a2 <\/em> a3 \u2026. * aK such that n = a1 + a2 + a3 \u2026 + aK and a1, a2, \u2026 ak > 0.<\/p>\n<\/blockquote>\n

SOLVING APPROACH:<\/h3>\n

This problem is similar to Rod Cutting Problem. We can get the maximum product by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.<\/p>\n

Can you think of the recursive function now?<\/strong><\/p>\n

maxProduct(n) = max(i(n-i), maxProductRec(n-i)<\/em>i)<\/strong> <\/p>\n

\n

for all i in {1, 2, 3 .. n},where maxProduct(n) is the maximum product of divisions of n.
\nRefer to this image for better understanding.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

You are encouraged to implement the above brute force on your own first ,before looking at the solution.
\n<\/strong><\/u><\/a><\/p>\n

Overlapping Subproblems:<\/h3>\n
\n

Let\u2019s consider the conditions for using DP to find an efficient solution:
\nOverlapping Sub-problems<\/strong> \u2014 Yes. From the image above ,you can notice the overlapping subproblems. When you implement using recursion, each subproblem will be computed several times.
\nOptimal Substructure<\/strong> \u2014 Yes. At each node in the call-tree, we\u2019re calling the recursive function on a smaller number. The decision which path to go down is based on the max product returned for each sub-problem.<\/p>\n

Recomputations of same subproblems can be avoided by constructing a temporary array dp[] in bottom up manner. <\/p>\n<\/blockquote>\n

O(n) approach:<\/h4>\n
\n

The idea is to break the number into multiples of 2 or 3. If you write the breaking results for couple of numbers like 7 to 10 you should get the idea. Assuming the max number is 60, there is a simple dynamic solution:<\/p>\n

int dp[60];\npublic:\nint integerBreak(int n)\n{\ndp[1]=1,dp[2]=1,dp[3]=2,dp[4]=4,dp[5]=6,dp[6]=9;\nfor(int i=7;i<=n;i++)\ndp[i]=max(dp[i-3]*3,dp[i-2]*2);\nreturn dp[n];\n}<\/code><\/pre>\n
SOLUTIONS:<\/h3>\n<\/blockquote>\n
\t\t\t\t\t\t