01 Knapsack Ca0759

Question: **0/1 Knapsack Problem Explanation and Dynamic Programming Solution** **Problem Statement** - Knapsack capacity: 7 kg - Five items each with given weight and profit - Goal: maximize total profit without exceeding capacity - 0/1 knapsack: items either taken whole or not at all - Different from fractional knapsack where fractions allowed **Brute Force Approach** - Try all combinations by including or excluding each item - Exponential time complexity - Impractical for large inputs **Dynamic Programming Approach** - Use bottom-up method with a table - Rows: items, Columns: capacities from 0 to 7 - Table cell: max profit achievable with given capacity and items considered - First row and column initialized to zero (no items or zero capacity) **Step-by-Step Table Filling** 1. First item (weight 3, profit 50): - Capacities 1 and 2: 0 (weight > capacity) - Capacity 3 to 7: 50 (item fits) 2. Second item (weight 2, profit 40): - Capacity 1: 0 (too small) - Capacity 2: max(0,40) = 40 - Capacity 3: max(50,40) = 50 - Capacity 4: 50 - Capacity 5: max(50,50+40) = 90 - Capacities 6 and 7: 90 3. Third item (weight 4, profit 70): - Capacities 1 to 3: copy above row - Capacity 4: max(50,70) = 70 - Capacity 5: max(90,70) = 90 - Capacity 6: max(90,40+70) = 110 - Capacity 7: max(90,50+70) = 120 4. Remaining items filled similarly by comparing current profit with above row **Determining Included Items** - Start from last cell (max profit 120) - Compare value above: - If same, item not included - If different, item included; subtract item profit and continue - Result: items 1 and 3 included **Complexity** - Time and space complexity: $O(n \times W)$ where $n$ is number of items and $W$ is capacity If you want to access the full transcript press the button bellow imagine we have a knapsack with a weight capacity of 9 kg we also have a set of items each with a specific weight and profit our goal is to select items in a way that maximizes the total profit while ensuring that the total weight does not exceed the knapsacks capacity the term 01 in this problem means that we can either take an item completely or leave it entirely we cannot take fractions of an item this is different from the fractional knapsack problem where we are allowed to take a portion of an item I have already made a video on fractional napsack you can check it out the link is in the description a simple way to solve this problem is by using Brute Force we start by either selecting the first item or skipping it then we repeat this process for the second item and so on until we reach the last item this approach explores all possible combinations which leads to an exponential time complexity because of this it is highly inefficient and impractical for large inputs now let's see how we can optimize this problem using the dynamic programming approach to make it more efficient in this example we have five items each with a specific weight and profit for ease of Animation let's set the knapsack capacity to seven we will use the bottom up approach to solve this problem if you're not familiar with this approach I recommend watching the video on introduction to dynamic programming first you can find the link in the description first we'll create a table where columns represent the weight capacities of the napsack rows represent the available items each entry in the table stores the maximum total profit achievable for a given capacity and the items considered so far the first row and the First Column represent the case where no items are available so their values are set to zero now let's start filling the table row by row beginning with the first item this item has a weight of three and a profit of 50 looking at the First Column where the capacity is one the item's weight is three which exceeds this capacity so we cannot place it in the knapsack and we set the value to zero moving to the next column where the capacity is two again the item's weight is greater than the capacity so we set the value to zero now for capacity 3 since the item's weight matches the capacity we can store it the profit for this item is 50 since there are no previous items We compare it with the value just above which is zero and take the maximum so we update this cell to 50 for all remaining columns in this row there are still no other items to consider so we simply carry forward this value which is 50 thus this row represents the case where only the first item is available now moving to the second item which has a weight of Two and a profit of 40 we'll start filling the corresponding Row in the First Column the capacity is one since this is less than the item's weight we cannot place it in the napsack so we set the value to zero next we move to the column where the capacity is two this can hold the current item comparing the current profit with the value above we see that the current profit is 40 which is greater than zero so we update this cell to 40 and move to the next one now the capacity is three the current item's weight is two with a profit of 40 however the previous row already has a profit of 50 Which is higher so we keep the value as 50 and move to the next column the capacity is now four the value from the row above is still 50 so we keep it at 50 as well now the next column has a capacity of five this one is interesting because it can hold both item one and item two together they give a total profit of 90 which is greater than the value from the row above so we update this cell to 90 for all the remaining columns we simply carry forward this value as 90 is the best profit we can achieve so far now moving on to the next item it has a weight of four and a profit of 70 so we start filling this Row for columns with capacities up to three we simply copy the values from the row above since the napsack cannot hold this item yet now for the column where the capacity is four We compare the current profit which is 70 with the profit from the row above which is 50 since 70 is greater we update this cell to 70 next we move to the column with a capacity of five the current profit remains 70 because we cannot add anything else this item alone weighs four however the profit from the row above is 90 since it can hold both item one and item two whereas the current row Can Only Hold item three so we update this cell to 90 now for the column where the capacity is six this can hold both item two and item three giving a combined profit of 110 since this is greater than the previous 90 we update the cell to 110 next for the column with a capacity of seven we can include item three and item one together they give a total profit of 120 Which is higher than the previous value of0 and certainly greater than the above value of 90 so we update this to 120 Now we move on to the next item the algorithm will similarly check whether the current profit is greater than the previous ones and update the cells accordingly I will pause the voiceover until the algorithm finishes once the table is generated the last element represents the maximum profit value in this case it is 120 now that we have found the max maximum profit value another problem is to determine which items were added to the knapsack using this table this is very easy to find we start by checking the element just above the last element here the last element is 120 and the value above it is also 120 since the value remains unchanged this indicates that the current item is not making a difference so this item is not included in the napsack we continue checking the previous item again the value above is the same meaning this item is also not included next we find an element where the value above is different here the value above is 90 which means the current item is making a difference this tells us that item three is present in the napsack since this item has a profit of 70 it contributes 70 to the total profit now subtracting 70 from2 gives 50 we then look for 50 in the above row and continue performing the same steps to to determine the remaining items here the value in the cell above is also 50 which means the current item is not included in the napsack so we move to the next item above now the value in the above cell is zero this means the current item is making a difference and is included in the napsack so finally we conclude that item three and item one are included in the napsack now the table contains n rows and W columns and we need to Traverse this table once so both the time and space lexity here is Big O of w * n check the GitHub Link in the description to get the python code for this problem