Difficulty: Medium
Pre-requisites: Dynamic Programming
Problem link:
Problem:
To maximize the profit by dividing a given length of thread.
Explanation:
It is similar to Unbounded 0/1 Knapsack Problem which can be solved using Dynamic Programing.
The total length of thread can be considered to as the total weight of Knapsack and every length as an item.
As we are talking about unbounded knapsack so for each length we find the maximum profit that can be obtained
for(i=0; i< wLen; i++){ //an iteration for each length</br>
if(w > W){ // w is the knapsack weight</br>
best=(K[w-W[i]]+V[i]>best)?(K[w-W[i]]+V[i]):best;</br>
}</br>
k[w]=best;</br>
}
Problem setter’s solution: SOLUTION