Interview Bootcamp
Vote

0% completed

​

Solution: 0/1 Knapsack

Introduction

Given the weights and profits of 'N' items, we are asked to put these items in a knapsack that has a capacity 'C'. The goal is to get the maximum profit from the items in the knapsack. Each item can only be selected once, as we don't have multiple quantities of any item.

Let's take Merry's example, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:

Items: { Apple, Orange, Banana, Melon }
Weights: { 2, 3, 1, 4 }
Profits: { 4, 5, 3, 7 }
Knapsack capacity: 5

.....

.....

.....

Like the course? Get enrolled and start learning!
G

greenwald.juj

· 3 years ago

DP - Bottom Up - Tabulation Solution

In the below example, aren't you already initializing the array to 0? So isn't the next for-loop to populate with 0's repetitive? Is there a reason to keep this?

    dp = [[0 for x in range(capacity+1)] for y in range(n)]
    
    # # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    for i in range(0, n):
      dp[i][0] = 0
Show 1 reply
Rohit Bhanot

Rohit Bhanot

· a month ago

Please include atleast couple of input/output examples which makes it easier to understand the problem if you are seeing it for the first time, otherwise one has to hop over to Leetcode or google it to see what the problem is all about. In this case the problem statement is very abstract and not easily understandable.

L

Learner

· 5 years ago

I have to say, jumping straight to recursion and not spending time to step through it/explain it is quite discouraging for beginners. To make matters more confusing, no differentiation between brute forcing via 4C4 + 4C3 + 4C2 + 4C1 + 4C0 = 16 as you have in the example, versus 4! = 24 and trying those combinations.

Show 1 reply
R

Ray

· 4 years ago

In the Bottom-up Dynamic Programming example, the diagram is confusing.

I understand with 0 capacity (the column), you have 0 profit.

I'm having a hard time understanding why the row (index 0) gets filled with all 1's. There are 4 items (various weights & profits). Does the index mean item count? If so, you should be able to have more profit with more capacity in the 1st row. It shouldn't be filled with all 1's. So I am not understanding the diagram ( https://lwfiles.mycourse.app/systemdesign-public/10cd89386658f0f18522e58386389d80.png ).

Show 2 replies
C

camelBack

· 3 years ago

Why is there a "+1" to the capacity when generating the 2d matrix? (the recursive, dynamic programming solution)

dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def solveKnapsack(self, profits, weights, capacity):
    
    def solve(index, acc_weight, memo):
      if index in memo and acc_weight in memo[index]:
        return memo[index][acc_weight]

      if index == len(profits):
        return 0 

      with_item = 0
      if acc_weight + weights[index] <= capacity:
        with_item = solve(index + 1, acc_weight + weights[index], memo) + profits[index]

      without_item = solve(index + 1, acc_weight, memo)
      
      result =  max(with_item, without_item)
      if index not in memo:
        memo[index] = {}
      memo[index][acc_weight] = result
      return result

    return solve(0, 0, {})