Knapsack problem 0-1

Intro

Also called the bagpack problem.

Intuition

• Two nested for loops, first for number of items and second for weights
• In Initialisation phase declare dp array of length till maximum weight, with all values as 0
• Is there is more difference in the weight, will the time complexity increase more?
• Now the zero values will start getting replaced with weight.
• In thetermination_phase the value at index equal to weight of bag in dp array will be returned.

Explanation

• Consider the same cases as mentioned in the recursive approach.
• In a DP[][] table let’s consider all the possible weights from ‘1’ to ‘W’ as the columns and weights that can be kept as rows. Table columns denote possible weights based on range and rows contain actual value.
• The state DP[i][j] will denote the maximum value of ‘j-weight’ considering all values from ‘1 to ith’. So if we consider ‘wi’ (weight in ‘ith’ row) we can fill it in all columns which have ‘weight values > wi’. For the rows the values are getting updated such that they have Max value of j subtracted by weight.
• Now two possibilities can take place:
• Fill ‘wi’ in the given column.
• Do not fill ‘wi’ in the given column.
• Now we have to take a maximum of these two possibilities, formally if we do not fill the ‘ith’ weight in the ‘jth’ column then the DP[i][j] state will be the same as DP[i-1][j] but if we fill the weight, DP[i][j] will be equal to the value of ‘wi’+ value of the column weighing ‘j-wi’ in the previous row.
• So we take the maximum of these two possibilities to fill the current state.

Code

def knapSack(maxWeight, weights, values, numItems):  
    dp = [0 for _ in range(maxWeight + 1)]  # Dynamic programming array
  
    for i in range(1, numItems + 1):  # Iterating over the items
        for w in range(maxWeight, 0, -1):  # Iterating over the weights in reverse order
            if weights[i - 1] <= w:  
                curValue = dp[w - weights[i - 1]] + values[i - 1]  # Calculating the current value
                dp[w] = max(dp[w], curValue)  
  
    return dp[maxWeight]  # Returning the maximum value of the knapsack  
  
# Driver code  
  
values = [60, 100, 120]  
weights = [10, 20, 30]  
maxWeight = 50  
numItems = len(values)  
  
print(knapSack(maxWeight, weights, values, numItems))

• sort by values
• pick most valuable item, keep filling with other valuable till bag weight is not remaining

Time complexity- O( $n^2$)

Rough