Basic Solution

This problem can be mapped to the "Unbounded Knapsack" pattern. The 'Weights' array of the Unbounded Knapsack problem is equivalent to the 'Lengths' array, and Profits is equivalent to Prices.

A basic brute-force solution could be to try all combinations of the given rod lengths to choose the one with the maximum sale price. This is what our algorithm will look like:

for each rod length 'i' 
  create a new set which includes one quantity of length 'i', and recursively process 
      all rod lengths for the remaining length 
  create a new set without rod length 'i', and recursively process for remaining rod lengths
return the set from the above two sets with a higher sales price 

Since this problem is quite similar to "Unbounded Knapsack", let’s jump directly to the bottom-up dynamic solution.

Bottom-up Dynamic Programming

Let's try to populate our dp[][] array in a bottom-up fashion. Essentially, what we want to achieve is: "Find the maximum sales price for every rod length and for every possible sales price".

So for every possible rod length 'len' (0<= len <= n), we have two options:

1. Exclude the piece. In this case, we will take whatever price we get from the rod length excluding this piece => dp[index-1][len]
2. Include the piece if its length is not more than 'len'. In this case, we include its price plus whatever price we get from the remaining rod length => prices[index] + dp[index][len-lengths[index]]

Finally, we have to take the maximum of the above two values:

    dp[index][len] = max (dp[index-1][len], prices[index] + dp[index][len-lengths[index]]) 

Let’s draw this visually, with the example:

Lengths: [1, 2, 3, 4, 5]  
Prices: [2, 6, 7, 10, 13]  
Rod Length: 5 

Let’s start with our base case of zero size: