{"id":2039,"date":"2020-07-29T08:32:24","date_gmt":"2020-07-29T08:32:24","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2039"},"modified":"2022-03-23T07:50:42","modified_gmt":"2022-03-23T07:50:42","slug":"toys","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/toys\/","title":{"rendered":"TOYS"},"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 :<\/h3>\n
\n

Once upon a time, Arya visited a toy store. As Arya is a small kid he is attracted to every toy. But Arya has a bag of capacity C and each toy occupies a definite volume of his bag. He would like to fill his bag so that when he goes home he can play with them all.
\nArya plays with each toy turn by turn and after playing with a specific toy his happiness increases by a specified amount which is different for a different toy.
\nAs a smart kid Arya wants to be the happiest person, help him to choose his toys. Each toy can be selected just one time.
\nFind the maximum value of happiness Arya can reach.<\/p>\n<\/blockquote>\n

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

EXPLANATION:<\/h3>\n
\n

NOTE: This is basically a modification of knapsack problem.<\/p>\n<\/blockquote>\n

BRUTE FORCE:<\/h4>\n
\n

Brute force is a straightforward approach to solving a problem, usually directly based on the problem\u2019s statement and definitions of the concepts involved. If there are n items to choose from, then there will be 2<\/code>n<\/code><\/sup>
\npossible combinations of items for the knapsack. An item is either chosen or not chosen. A bit string of 0\u2019s and 1\u2019s is generated which is of length n. If the ith symbol of a bit string is 0, then the ith item is not chosen and if it is 1,
\nthe ith item is chosen.<\/p>\n<\/blockquote>\n

ALGO:<\/h4>\n
   let w[1], ... , w[n] be the weights of the items\n   let v[1], ... , v[n] be the values of the items\n   let maxWeight be the capacity of the bag\n   bestValue := 0\n   function solve(n, currentWeight, currentValue) {\n    if n = 0 and currentWeight <= maxWeight and currentValue     bestValue:\n        bestValue := currentValue\n    if n = 0: return\n    don't pack this item\n    solve(n-1, currentWeight, currentValue)\n     pack this item\n    solve(n-1, currentWeight + w[n], currentValue + v[n])\n    }\n    solve(n, 0, 0)\n    print bestValue<\/code><\/pre>\n
You are encouraged to implement the above brute force before looking at the solution.<\/strong><\/p>\n
\n
What did you get?TLE?
\nYou got TLE because if you observe closely , you could easily see that this approach takes O(N*2n<\/sup>)<\/p>\n<\/blockquote>\n
OPTIMIZATION:<\/h3>\n
DYNAMIC PROGRAMMING:<\/h4>\n
\n
Here\u2019s the general way the problem is explained \u2013 Consider a thief gets into a home to rob and he carries a knapsack. There are fixed number of items in the home \u2013 each with its own weight and value \u2013 Jewellery, with less weight and highest value vs tables, with less value but a lot heavy. To add fuel to the fire, the thief has an old knapsack which has limited capacity. Obviously, he can\u2019t split the table into half or jewellery into 3\/4ths. He either takes it or leaves it.<\/p>\n
Had it not been so,we could have easily used greedy approach.<\/p>\n
The way this is optimally solved is using dynamic programming \u2013 solving for smaller sets of knapsack problems and then expanding them for the bigger problem.<\/p>\n
We will use two variables to represent the states of DP.<\/p>\n
i<\/code> \u2013 The current index we are working on.<\/p>\n
R<\/code> \u2013 It contains the remaining capacity of each and every knapsack.<\/p>\n
Now, at each step, we will have k+1 choices.<\/p>\n
Reject index i<\/code>.<\/p>\n
Put item i<\/code> in knapsack 1.<\/p>\n
Put item i<\/code> in knapsack 2.<\/p>\n
Put item i<\/code> in knapsack 3.
\n\u2026
\nk+1<\/code>) Put item i<\/code> in knapsack k.<\/p>\n<\/blockquote>\n
In simpler words<\/strong><\/p>\n
\n
The knapsack problem is a problem in combinatorial optimization: given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items . The most famous knapsack problem is the binary (<\/code>0\u20131)<\/code> knapsack problem, where the decision maker is allowed to pick (1) or not to pick (0) the item, in other words, the items are not dividable.<\/p>\n
The problem can be formulated as follows:<\/p>\n
Let there be N items, x1 to xn where xi has the vi value and wi weight . The maximum weight the knapsack can carry is W. It is common to assume that all values and weights are non-negative. <\/p>\n
To illustrate, assume w1,w2,w3..wn are strictly positive integers. Define m[i,w] to be the maximum value that can be attained when the weight is less than or equal to  w using items up to i. The definition of  is then as follows:<\/p>\n<\/blockquote>\n
    \n
  1. m[i,w]<\/code> =<\/code> m[i-1,w]<\/code> if wi<\/code>>w<\/code>(the new item is more than the current weight limit)<\/li>\n
  2. m[i,w]<\/code> =<\/code> max(<\/code> m[i-1,w]<\/code> ,m[i-1,w-wi]+vi<\/code> )<\/code> if wi<\/code> `<\/li>\n<\/ol>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t