Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

0/1 Knapsack

Problem Statement

Try it yourself

Problem Statement

Given two integer arrays to represent weights and profits of 'N' items, we need to find a subset of these items which will give us maximum profit such that their cumulative weight is not more than a given number 'C'. Write a function that returns the maximum profit. Each item can only be selected once, which means either we put an item in the knapsack or skip it.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
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
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, {})
Rohit Bhanot

Rohit Bhanot

· 12 days 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.

On This Page

Problem Statement

Try it yourself