Problem 6 You have decided to move into storage store to purchase containers in
ID: 3596265 • Letter: P
Question
Problem 6 You have decided to move into storage store to purchase containers in which to pack your nu textbooks. Assume exceed W, e.g. W = 100 pounds. a new apartment but to do so, you will need to stop at the box cach container can hold a vertical stack of books whose total weight does not lcontainers and they cost a lot of money, so you'd like to buy only as many as you need. Your textbooks have respective weights of wi,W2,Wy and any combination of them can be vertically stacked into a box as long as the total wei not exceed W ght does a. The moving company is coming in two days to pick up your boxes. Describe a greedy algorithm that can be used to determine how many you will need for packing your n books. b. What is the time complexity of your approach?Explanation / Answer
The given problem is similar to the 0/1 knapsack problem where we have n items and we need to put these items in a knapsack of maximum capacity W such that we get the maximum value for the knapsack and as the items(books) are indivisible.
The fractional knapsack takes a greedy algorithm approach, but can take the fractional part of items in order to optimally fill the weight W, which in our case is not possible (you can tear the pages of your book, but you should not!)
0/1 knapsack problems are solved using dynamic programming.
2 major aspect of the algorithm is:
Nested optimal solution of the problem contained within it’s optimal solution to subproblem
Let KNAP(1,n,W) denote the 0/1 knapsack problem choosing objects from 1..n under the capacity constraint of W.
If(x1,x2,…xn) is an optimal solution for the problem KNAP(1,n,W) then
When same sub problem will be visited again and again.
Algorithm:
We will build table K[][] in bottom up manner to store the item’s weight in order to their occurrence while they are fulfilling the criteria to be put in the box of maximum able contain max weight of W.
For i=0 to n {
For weight w=0 to W {
If I is zero or weight w is zero
K[i][w]=0
Else if weight[i-1] is less than equal to w
K[i][w]=max of w[[i-1]+k[i-1][w-wt[i-1]] and k[i-1][w]
Else k[i][w]=k[i-1][w]
}
}
Total time complexity:
As we can see there are 2 for loop for 1 for number of items and other up to max weight W
i.e. O(nW) where n is the number of items and W is capacity of knapsack.