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 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:
where
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
- Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
- Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
- Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
- Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
- Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
- Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
- Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
- Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
- Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
- Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
- Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
- Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
- Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
- Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
- Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
- Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
- Complete Knapsack Problem
- 0/1 Knapsack Problem
- Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
- Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
- Using BackTracking Algorithm to Find the Combination Integer Sum
- Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
- Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP
–EOF (The Ultimate Computing & Technology Blog) —
loading...
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