Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers prices where prices[i] represents the price to sell a rod of size i + 1, and an integer n which represents the current size of the rod.

Given you can cut the rod into any number of different sizes, return the maximum profit that can be earned.

Constraints
m = n ≤ 1000 where m is the length of prices.
Example 1
Input
prices = [1, 3, 5, 7, 7, 7]
n = 6
Output
10
Explanation
The price table shows that we can:
Sell a rod of size 1 for price of 1
Sell a rod of size 2 for price of 3
Sell a rod of size 3 for price of 5
Sell a rod of size 4 for price of 7
Sell a rod of size 5 for price of 7
Sell a rod of size 6 for price of 7
The optimal way to cut the rod is to split it into 2 pieces of length 3, to achieve profit of 10.

Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm

We let tex_878f71de1e4f1a6da961d533f43d026e Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm algorithms dynamic programming Dynamic Programming Knapsack Problems math python teaching kids programming youtube video represent the max profit for the size-n rod. We can seek to have the first cut i which can be range from 0 to n-1 (thus size is i+1). The remaining size is n-1-i and we can recursively solve this (as this is a smaller input). The profit of the first cut is price[i] and we can compare and store the maximal profit of those N cuts.

Recursion with Memoization is Top Down Dynamic Programming. And this can be also seen as a unbounded knapsack problem where the knapsack has capacity N, and we have items of size 1, 2, 3, … N and their values are known. We want to pack the knapsack where each item we can pick as many as we want. The target is to maximize the values of the knapsack.

The Dynamic Programming equation is:

tex_c6a598664d6740124dda131595159630 Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm algorithms dynamic programming Dynamic Programming Knapsack Problems math python teaching kids programming youtube video where tex_37b93a4d0c412f1c44f88cc3bcb41359 Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm algorithms dynamic programming Dynamic Programming Knapsack Problems math python teaching kids programming youtube video

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfitUnboundedKnapsack(self, prices, n):        
        @cache
        def f(n):
            if n<= 0:
                return 0
            ans = 0
            for i in range(n):
                ans = max(ans, f(n- i - 1) + prices[i])
            return ans
        return f(n)
class Solution:
    def maxProfitUnboundedKnapsack(self, prices, n):        
        @cache
        def f(n):
            if n<= 0:
                return 0
            ans = 0
            for i in range(n):
                ans = max(ans, f(n- i - 1) + prices[i])
            return ans
        return f(n)

We use the @cache to let the computer store the values for us. The time complexity is O(N^2) quadratic (e.g. polynomial time) as for each f(N) value we need to iterate N times. And the space complexity is O(N) as there are at most N values to store.

We can solve this unbounded knapsack using Bottom Up Dynamic Programming Algorithm: Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
725 words
Last Post: Teaching Kids Programming - Split Tree to Maximize Product (Recursive Depth First Search Algorithm)
Next Post: Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm

The Permanent URL is: Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm

Leave a Reply