Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Unbounded Knapsack

Introduction

Problem Statement

Try it yourself

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. The only difference between the "0/1 Knapsack" problem and this problem is that we are allowed to use an unlimited quantity of an item.

Let's take the example of Merry, 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, Melon }
Weights: { 1, 2, 3 }
Profits: { 15, 20, 50 }
Knapsack capacity: 5

Let's try to put different combinations of fruits in the knapsack, such that their total weight is not more than 5.

5 Apples (total weight 5) => 75 profit
1 Apple + 2 Oranges (total weight 5) => 55 profit
2 Apples + 1 Melon (total weight 5) => 80 profit
1 Orange + 1 Melon (total weight 5) => 70 profit

This shows that 2 apples + 1 melon is the best combination, as it gives us the maximum profit and the total weight does not exceed the capacity.

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'. We can assume an infinite supply of item quantities; therefore, each item can be selected multiple times.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
G

Gary

· 4 years ago

Can you please elaborate on why the time complexity of the brute force solution is O(2 ^ N + C)?

G

Gary

· 4 years ago

For diagrams in "Bottom-up Dynamic Programming" section, shouldn't the captions be

Capacity = 3, Index = 0, => profits[Index] + dp[Index][Capacity - 1]

instead of

Capacity = 3, Index = 0, => profits[Index] + dp[Index][1] ?

Same for Capacity = 4-8, Index = 0 below that.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def solveKnapsack(self, profits, weights, capacity):

    def dp(index, acc, weight, memo):

      if (index, acc, weight) in memo:
        return memo[(index, acc, weight)]

      if index == len(profits):
        return acc
      
      result = 0
      if weight + weights[index] <= capacity:
        same_index = dp(index, acc + profits[index], weight + weights[index], memo)
        skip_index = dp(index + 1, acc, weight, memo)
        result = max(same_index, skip_index)
      
      else:
        result = dp(index + 1, acc, weight, memo) # skip index 

      memo[(index, acc, weight)] = result
      return result

    return dp(0, 0, 0, {})
Online Courses

Online Courses

· 4 months ago

My solution, slight modification of my 0/1 knapsack solution:

class Solution:
  def solveKnapsack(self, profits, weights, capacity):
    """
    Solves the unbounded knapsack problem using recursion.
    """
    n = len(profits)
    if n == 0:
      return 0
    
    # state
    dp = [0] * (capacity + 1)

    for idx in range(n - 1, -1, -1):
      for remaining in range(capacity + 1):
        # skip
        skip = dp[remaining]

        # take
        take = 0
        if weights[idx] <= remaining:
          take = profits[idx] + dp[remaining - weights[idx]]
        
        dp[remaining] = max(skip, take)
    
    return dp[capacity]

On This Page

Introduction

Problem Statement

Try it yourself