Input: A rod on X inches. Price list of Rod prices on n inches.

Problem: Cut a rod of X inches into pieces so that it can be sold at a maximum price.

Example

Input- 8 inch rod
Price list : 1 inch piece=1 Rs, 2=5, 3=8, 4=9, 5=10, 6=17, 7=17 and so on

Output= maximum price=22 (6+2 inch)


/**
* Problem definition: we need to calculate max revenue that can be generated by cutting
* a rod of given size (in inches)
* @author kamal
*
*/
public class CutRod {

//we will be given price based on an inch, 0 inch=0Rs, 1=1, 2=5 and so on
//append zeros where price is not known, so here we can sell max rod of 7 inches
private int prices[]={0,1,5,8,9, 10,17,17,0,0,0,0,0,0,0,0,0};//append n

//using dynamic programming, we will store any previously calculated max prices
private int revenue[]=new int[20];

/**
* Main Method
* @param s
*/
public static void main(String s[])
{
CutRod cr=new CutRod();
System.out.println(cr.fetchMaxPrice(8));
}

/**
* Recursively calls itself to fetch max price
* @param size
* @return
*/
private int fetchMaxPrice(int size)
{
int price=0;
if(size==0)
return 0;
if(revenue[size]>0)
return(revenue[size]);
//brute force
for(int i=1;i<=size;i++)


{

//ith cut price



price=getMax(price, prices[i]+this.fetchMaxPrice(size-i));

revenue[size]=price;

}


return price;

}



/**
* Returns maximum of 2 integers
* @param a
* @param b
* @return
*/


private int getMax(int a, int b)
{


if (a>=b)
return a;
else
return b;
}
}


In last post I discussed an algorithm to find out intersection point in 2 lists. A related problem to that is to figure out if a list has cycles. Say there are 10 nodes in list and 10th node is pointing back to 4th node. How ill we figure out if a list has such a cycle.

There can be many solutions, like storing previously traversed nodes, or simply adding a flag to each node indicating of the node was already traversed or not. But these solutions need extra space of order n.

A classic solution to above problem is ‘Tortoise and Hare algorithm’ or ‘Floyd’s cycle-finding algorithm’. The idea is to have two pointers, one will traverse list node by node or move one node at a time (tortoise) and another pointer moving two nodes at a time (hare). If the list has a cycle, the two pointers are bound to meet at some node, otherwise they will never meet. Try to dry run it, you will know what it means.

There are 2 lists A and B (we know the root nodes for both). We know that these 2 lists intersect at some point and after that it is common list (they merge into each other, or think of it as a Y list).

example: list A->1->2->3->4->5->6->end
List B->11->12->4->5->6->end

Both the list intersect at node 4. This is what we need to find.

Solution-
1. Find length of A
2. Find length of B
3. Find diff=length A-length B
4. Traverse larger list diff nodes (we know after this nodes will be equal for both lists).
5. Now traverse both list simultaneously and find out the common node (this is our required node).

More solutions here.

I like the solution 5 as well from solution lists. It is simply reversing the list A (6->5->4->-3->2->1).

So when we are traversing list 2 now we will get like 11->12->4->3->2->1->end (as the pointers are reversed). So we are actually calculating length(sum) of non-common part, And we already know length of 2 lists.

length A=A’+C(Common part)
length B=B’+C
and A’+B’=L (length of non-common part we found by traversing list B after reversing list A)

Three unknowns(A’, B’ and C) and three equations. Can’t get simpler than this.