SILK - EDITORIAL

Difficulty: Medium

Pre-requisites: Dynamic Programming

Problem link:

Contest problem link

Practice 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

//