Tuesday 3rd of December 10:38:42pm
Tuesday 3rd of December 10:38:42pm
Rod Cutting Dynamic Programming in c/cpp
----------------------------------------------
#include<iostream>
#include<stdio.h>
#include <math.h>
int cutRod(int price[], int n);
int max(int a, int b);
using namespace std;
int main()
{
int arr[] = {1,5,8,9};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum Obtainable Value is %d ", cutRod(arr, size));
getchar();
return 0;
}
int cutRod(int price[], int n)
{
int r[n];
r[0] = 0;
for (int j = 1; j<=n; j++)
{
int q = -INFINITY;
for (int i = 1; i <= j; i++)
q = max(q, price[i] + r[j-i]);
r[j] = q;
}
return r[n];
}
int max(int a, int b)
{
return (a > b)? a : b;
}
-------------------------------------------
BOTTOM-UP-CUT-ROD (p, n)
1 let r[O...n] be a new array
2 r[0]=0
3 for j = 1 to n
4 q = -Infinity
5 for i = 1 to j
6 q =max(q, p[i] +r [j-i]
7 r[j]=q;
8 return r[n]
--------------------------------------------------
BOTTOM-UP-CUT-ROD.p; n/
1 letrOE0: : n be a new array
2 rOE0 D 0
3 for j D 1 to n
4 q D 1
5 for i D 1 to j
6 q D max.q; pOEi C rOEj i /
7 rOEj D q
8 return rOEn
.webp)
