<jupyter_start><jupyter_text>Tutorial Topic: 0-1 Knapsack Name: <NAME> NUID: 002115486  0-1 KnapsackIn this tutorial we will see working and appplications of 0-1 Knapsack problem. 0-1 Knapsack approach is Dynamic Programming. First, lets see what exactly is dynamic programming.  Dynamic ProgrammingDynamic programming solves problems by combining the solutions to subproblems. It can beanalogous to divide-and-conquer method, where problem is partitioned into disjoint subproblems,subproblems are recursively solved and then combined to find the solution of the original problem.In contrast, dynamic programming applies when the subproblems overlap - that is, whensubproblems share subsubproblems. In this context, a divide-and-conquer algorithm does morework than necessary, repeatedly solving the common subsubproblems. A dynamic-programmingalgorithm solves each subsubproblem just once and then saves its answer in a table, therebyavoiding the work of recomputing the answer every time it solves each subsubproblems. Let's look at an example. Italian Mathematician <NAME>, whom we commonlyknow as Fibonacci, discovered a number series by considering the idealized growth of rabbitpopulation. The series is: 1, 1, 2, 3, 5, 8, 13, 21, ...... We can notice that every number after the first two is the sum of the two preceding numbers. Now,let's formulate a function F(n) that will return us the nth Fibonacci number, that means, F(n) = nth Fibonacci Number So far, we've known that, F(1) = 1F(2) = 1F(3) = F(2) + F(1) = 2F(4) = F(3) + F(2) = 3 We can generalize it by:<jupyter_code>F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)<jupyter_output><empty_output><jupyter_text>Now if we want to write it as a recursive function, we have F(1) and F(2) as our base case. So ourFibonacci Function would be: ![ngSbS.jpg](attachment:ngSbS.jpg) From the picture, we can see that F(6) will call F(5) and F(4). Now F(5) will call F(4) and F(3). Aftercalculating F(5), we can surely say that all the functions that were called by F(5) has been alreadycalculated. That means, we have already calculated F(4). But we are again calculating F(4) asF(6)'s right child indicates. Do we really need to recalculate? What we can do is, once we havecalculated the value of F(4), we'll store it in an array named dp, and will reuse it when needed.We'll initialize our dp array with -1(or any value that won't come in our calculation). Then we'll callF(6) where our modified F(n) will look like:<jupyter_code>Procedure F(n):
if n is equal to 1
 return 1
else if n is equal to 2
 return 1
else if dp[n] is not equal to -1 //That means we have already calculated dp[n]
 return dp[n]
else
 dp[n] = F(n-1) + F(n-2)
return dp[n]
end if<jupyter_output><empty_output><jupyter_text>We've done the same task as before, but with a simple optimization. That is, we've usedmemoization technique. At first, all the values of dp array will be -1. When F(4) is called, we checkif it is empty or not. If it stores -1, we will calculate its value and store it in dp[4]. If it storesanything but -1, that means we've already calculated its value. So we'll simply return the value. This simple optimization using memoization is called **Dynamic Programming.** A problem can be solved using Dynamic Programming if it has some characteristics. These are:    Subproblems:    A DP problem can be divided into one or more subproblems. For example: F(4) can be    divided into smaller subproblems F(3) and F(2). As the subproblems are similar to our main    problem, these can be solved using same technique.    Overlapping Subproblems:    A DP problem must have overlapping subproblems. That means there must be some    common part for which same function is called more than once. For example: F(5) and F(6)    has F(3) and F(4) in common. This is the reason we stored the values in our array. ![7OVJm.jpg](attachment:7OVJm.jpg) Optimal Substructure:Let's say you are asked to minimize the function g(x). You know that the value of g(x)depends on g(y) and g(z). Now if we can minimize g(x) by minimizing both g(y) and g(z),only then we can say that the problem has optimal substructure. If g(x) is minimized by onlyminimizing g(y) and if minimizing or maximizing g(z) doesn't have any effect on g(x), thenthis problem doesn't have optimal substructure. In simple words, **if optimal solution of aproblem can be found from the optimal solution of its subproblem, then we can say theproblem has optimal substructure property.**  Knapsack Problem **Explanation:** Suppose you woke up on some mysterious island and there are different precious items on it. Each item has a different value and weight. You are also provided with a bag to take some of the items along with you but your bag has a limitation of the maximum weight you can put in it. So, you need to choose items to put in your bag such that the overall value of items in your bag maximizes. ![knapsackMain.png](attachment:knapsackMain.png) This problem is commonly known as the knapsack or the rucksack problem. There are different kinds of items (i) and each item i has a weight (wi) and value (vi) associated with it. xi is the number of i kind of items we have picked. And the bag has a limitation of maximum weight(W). ![knap2.png](attachment:knap2.png) So, our main task is to maximize the value i.e., ∑ni=1(vixi) (summation of the number of items taken * its value) such that ∑ni=1wixi≤W i.e., the weight of all the items should be less than the maximum weight. There are different kind of knapsack problems:1. 0-1 Knapsack Problem → In this type of knapsack problem, there is only one item of each kind (or we can pick only one). So, we are available with only two options for each item, either pick it (1) or leave it (0) i.e., xi∈{0,1}.2. Bounded Knapsack Problem (BKP) → In this case, the quantity of each item can exceed 1 but can't be infinitely present i.e., there is an upper bound on it. So, 0≤xi≤c, where c is the maximum quantity of i we can take. 3. Unbounded Knapsack Problem (UKP) → Here, there is no limitation on the quantity of a specific item we can take i.e., xi≥0.4. Integer Knapsack Problem → When we are not available to just pick a part of an item i.e., we either take the entire item or not and can't just break the item and take some fraction of it, then it is called integer knapsack problem.5. Fractional Knapsack Problem → Here, we can take even a fraction of any item. For example, take an example of powdered gold, we can take a fraction of it according to our need.      0-1 Knapsack Problem Let's start by taking an example. Suppose we are provided with the following items: ![knap4.png](attachment:knap4.png) and the maximum weight the bag can hold is 5 units i.e., W=5. Since it is a 0-1 knapsack problem, it means that we can pick a maximum of 1 item for each kind. Also, the problem is not a fractional knapsack problem but an integer one i.e., we can't break the items and we have to pick the entire item or leave it. First take a case of solving the problem using brute force i.e., checking each possibility. As mentioned above, we have two options for each item i.e., either we can take it or leave it. ![knap3.png](attachment:knap3.png) So, you can see that this will take O(2n) time and we already know how bad an exponential running time is and thus there is no chance that we are going to use this as our solution. One can also think of a solution of always taking the item with the highest valueweight ratio first (known as greedy algorithm) but it is also not going to help here. As mentioned above, it could have helped in the case of the fractional knapsack problem. Let's first test this idea to see that it really doesn't work here. The item with the highest valueweight ratio is the 4th one, so we will pick it and then the 1st one. Now, we have a total value of 8+6=14 and a total weight of 3+1=4 units. We still have the space left to take more items having a total maximum weight of 1 unit but there is no such item left (each item left has a weight greater than 1), so this is what we can pick by using this technique. ![knap5.png](attachment:knap5.png) We can pick the 3rd and the 4th item with a total value of 9+6=15 and a total weight of 4+1=5 and beat the value of 14.So, let's find out another technique to solve this problem.Let's say there is only the first item available for us. If its weight is within the limit of the maximum weight i.e., w1≤W then we will pick it otherwise, not.Now, take the case when there are first two items available for us. If the weight of the second element is not within the limit i.e., w2>W, then we are not going to pick it. But if its weight is less than W, then we can either pick it or not. In case of picking it, the value of the second element (v2) will be added to the total value and we will now decide for the optimized value we can get from the first element for W−w2 weight limit and if we are not picking it, then we will decide for the first element for W weight limit. To get the maximum total value, we will choose the maximum of these two cases. ![knap6.png](attachment:knap6.png) Similarly, for the first three elements, we can't pick the third element if its weight is not within the limit i.e., w3>W and in this case, we will be left with the weight limit W and the first two items. If its weight is in the limit of the maximum weight, then we can either pick it or not. In case of picking it, the value of the third item (v3) will be added to the total value and now we have to get the total optimized value of the first two elements and weight limit of W−w3. In case of not picking it, we are just left with the first two elements and a weight limit of W. So, we will choose the maximum value from the latter two cases i.e., whether we are picking the 3rd item or not. ![knap7.png](attachment:knap7.png) Basically, we are developing a bottom-up approach to solve the problem. Let's say that we have to make a decision for the first i elements to get the optimized value. Now, there can be two cases - the first that the weight of the ith item is greater than the weight limit i.e., wi>W, in this case, we can't take this item at all, so we are left with first i−1 items and with the weight limit of W; the second case, when wi≤W, in this case, we will either take it or leave it.Let's talk about the second case. If we will pick the item, we will add the value of the ith item (vi) to the total value and then we are left with a total of first i−1 items and the total weight limit will reduce to W−wi for rest of the items. And if we don't pick it, even then we are left with the first i−1 items but the weight limit will be still W. And then we will choose the maximum of these two to get an optimized solution. ![knap8.png](attachment:knap8.png) Let's say F(i,w) is a function which gives us the optimal value for the first i items and weight limit w, so we can write F(i,w) as:F(i,w)={F(i−1,w),if wi >w or F(i,w)=max{F(i−1,w),(F(i−1,w−wi)+vi)},if wi≤w ![knap9.png](attachment:knap9.png) As you can see from the picture given above, common subproblems are occurring more than once in the process of getting the final solution of the problem, that's why we are using dynamic programming to solve the problem.As we are using the bottom-up approach, let's create the table for the above function.  Solution Table for 0-1 Knapsack Problem ![knap10.png](attachment:knap10.png) The rows of the table are representing the weight limit i.e., the optimal value for each weight limit and the columns are for the items. So, the cell (i, j) of the table contains the optimal value for the first i items and for a weight limit of j units. Thus, we are going to find our solution in the cell (4,5) i.e., first 4 items with a weight limit of 5 units.If the weight limit is 0, then we can't pick any item making so the total optimized value 0 in each case. This will also happen when i is 0, then also there is no item to pick and thus the optimized value will be 0 for any weight. ![knap11.png](attachment:knap11.png) Now, let's start filling up the table according to the function we have derived above.Starting from F(1,1),w1 = 3W =1w1 >WF(i,W)=F(i−1,W)F(1,1)=F(0,1)=0Similarly, F(1,2)=F(0,2)=0. ![knap12.png](attachment:knap12.png) For F(1,3),w1=3 and W=3F(i,W)=max{F(i−1,W),(F(i−1,W−wi)+vi)}F(1,3)=max{F(0,3),(F(0,0)+8)}=max{0,8}=8and so on. ![knap13.png](attachment:knap13.png) F(2,3)=max{F(1,3),(F(1,1)+3)}=max{8,3}=8 ![knap18.png](attachment:knap18.png) Similarly, ![knap19.png](attachment:knap19.png) So, you can see that we have finally got our optimal value in the cell (4,5) which is 15.<jupyter_code>cost = [[0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0]]

def knapsack(n, W, wm, vm):
    for i in range(1, n+1):
        for w in range(1, W+1):
            if(wm[i] > w):
                cost[i][w] = cost[i-1][w]
            else:
                if ((vm[i]+cost[i-1][w-wm[i]]) > cost[i-1][w]):
                      cost[i][w] = vm[i] + cost[i-1][w-wm[i]]
                else:
                      cost[i][w] = cost[i-1][w]
    return cost[n][W]

if __name__ == '__main__':
  # element at index 0 is fake. matrix starting from 1.
  wm = [0, 3, 2, 4, 1]
  vm = [0, 8, 3, 9, 6]
  print(knapsack(4, 5, wm, vm))<jupyter_output>15<jupyter_text>Analysis for Knapsack Code The analysis of the above code is simple, there are only simple iterations we have to deal with and no recursions. The first loops (for w in 0 to W) is running from 0 to W, so it will take O(W) time. Similarly, the second loop is going to take O(n) time.Now, while iterating on the matrix, each of the statements is a constant time taking statement. And for every iteration of the first loop from 1 to n, the nested loop will be executed 1 to W times, thus it will take O(n∗W) time.Also, the last statement (return cost[n, W]) is going to take constant time.Since O(nW) easily dominates O(n) and O(W), so our algorithm has a running time of O(nW).  knapsack for Internet Download ManagerOne application for knapsack is Internet Download Manager where data is broken into chunks and as per the maximum size of data that can be retrieved in one go .The server uses this algorithm and packs the chunks so as to utilize the full size limit.The simple solution is to consider all subsets of item and calculate total weight and value of all subsets. Consider the only subset whose weight is smaller than W. Then pick the maximum value subset from all those subset.Substructure Solution:For considering all subsets of items, there can be two cases for every item:(1) the item is included in subset(2) not included in the optimal set.That's why the maximum value that can be obtained from n items is maximum of two values. 1) Maximum value obtained by n-1 items and W weight (excluding nth item). 2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility. Dynamic Programming:Problem Statement :Suppose we have a knapsack which can hold int w = 10 weight units. We have a total of int n = 4 items to choose from, whose values are represented by an array int[] val = {10, 40, 30, 50} and weights represented by an array int[] wt = {5, 4, 6, 3}.Since this is the 0–1 knapsack problem, we can either include an item in our knapsack or exclude it, but not include a fraction of it, or include it multiple times.Solution :Step1:We can create a 2-D array of n + 1 rows and w + 1 columns.Let i be the row number that represents the set of all the items from rows 1—i .Let j (column number)represents the weight capacity of our knapsack.Putting everything together, an entry in row i, column j represents the maximum value that can be obtained with items 1, 2, 3 …i, in a knapsack that can hold j weight units.Step 2:The base cases, for which the solution is trivial. For instance, at row 0, when we have no items to pick from, the maximum value that can be stored in any knapsack must be 0. Similarly, at column 0, for a knapsack which can hold 0 weight units, the maximum value that can be stored in it is 0. (We’re assuming that there are no massless, valuable items.)We can do this with 2 for loops: ![phpmGFAE3.png](attachment:phpmGFAE3.png) Recursive Approach :In recursion tree, K() refers to knapSack().  The two parameters indicated in the following recursion tree are n and W. The recursion tree is:wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}                       K(3, 2)         ---------> K(n, W)                   /            \                  /                \                           K(2,2)                  K(2,1)          /       \                  /    \         /           \              /        \       K(1,2)      K(1,1)        K(1,1)     K(1,0)       /  \         /   \          /   \     /      \     /       \      /       \K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.<jupyter_code>def knapSackDynamic(WeightCapacity, wt, val, n):
    K = [[0 for x in range(WeightCapacity + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(WeightCapacity + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    return K[n][WeightCapacity]

def knapSack(W, wt, val, n):
    if n == 0 or W == 0 :
        return 0
    if (wt[n-1] > W):
        return knapSack(W, wt, val, n-1)
    else:
        return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                   knapSack(W, wt, val, n-1))   

# Program to test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSackDynamic(W, wt, val, n))
print(knapSack(W , wt , val , n) )<jupyter_output>220
220
{'fraction_non_alphanumeric': 0.0796058458813109, 'fraction_numerical': 0.023472099202834367, 'mean_word_length': 3.507235528942116, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '557213', 'license': 'CC0-1.0', 'n_tokens_mistral': 5615, 'n_tokens_neox': 5236, 'n_words': 2942, 'path': 'I2A_Algorithms/I2A_Dynamic_Programming/I2A_0_1_Knapsack_Problem.ipynb', 'repo_name': 'aiskunks/Skunks_Skool', 'size': '18097'}