CareerCup

This can be solved using dynamic programming, you can look at the solution to this problem in this very good video tutorial

youtube.com/watch?v=U-09Gs6cbsQ

done using dynamic programming

//it contains max price possible for each length
int maxPrice[N+1]={0};    
int i=1;
while(i<=N)
{
       for(int j=0;j<i;j++)
       {
                 if(maxPrice[i]<(maxPrice[j]+price[i-j]))
                 {
                      maxPrice[i]=maxPrice[j]+price[i-j];
                 }
       }
i++;
}
return maxPrice[N];

This can be solved using dynamic programming, you can look at the solution to this problem in this very good video tutorial

youtube.com/watch?v=U-09Gs6cbsQ

See Cormen , Page - 360...by Dynamic Programming

clrs pd problem rod cut

Can't it be done using all pairs shortest paths problem in graph?
Initially take all edges to be of length 1 as in the given example.

While relaxing, take the price of that length rather than just length and do it. Somone please say if I'm wrong

Can't it be done using all pairs shortest paths problem in graph?
Initially take all edges to be of length 1 as in the given example.

Instead of taking min(D[i,j],D[i,k]+D[k,j]), take min(PRICE(D[i,j]),PRICE(D[i,k]+D[k,j])), take the price of that length rather than just length and do it. Somone please say if I'm wrong

Isn't this an oral question.

You divide the rod in

(int) N / 6

pieces of 6. Then for the remaining

N % 6

pieces devide as follows

1 -- 1
2 -- 2
3 -- 3
4 -- 2, 2
5 -- 2, 3

it is essentially equivalent of 0/1 knapsack problem
where
lengths array coreespond to weight
value correspond to value/profit
input lenght of rod correspond to the capacity of knapsack

#include<stdio.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int length[]={0,1,2,3,4,5,6,7,8};
    int price[]={0,1,5,8,9,10,17,17,20};
    int n=sizeof(price)/sizeof(*price);
    int N=12,i,L;
    int cut[N+1];
    for(i=0;i<=N;i++)
        cut[i]=price[1]*i;
    for(i=2;i<=N;i++){
      for(L=2;L<=n && L<=i;L++){
          if(L==i)
             cut[i]=max(cut[i],price[L]);
          else
             cut[i]=max(cut[i],cut[L]+cut[i-L]);
      }
    }
    printf("%d\n",cut[N]);
    return 0;
}

calculate price/length: for the given example it is..
1, 2.5, 2.67 , 2.25, 2, 2.42, 2.125, 2.5

here the length 3 have maximum price.. cut the piece of length N into pieces of length 3..
Benefit = number_of_pieces * 2.67

in addition there may be piece of length 2 or 1 give rise to additional cost of 2.5 or 1..