Need help of dynamic programming rod cutting? c++????? this is the verifier.cpp

Question

Need help of dynamic programming rod cutting? c++?????

this is the verifier.cpp

#include <iostream>

using namespace std;

int main(int argc,char **argv) {

// Get the size of the sequence
int n = 1;
int* p;

cin >> n;

p = new int[n+1];
//read p;
p[0] = 0;
for(int i=1; i<=n; i++)
{
cin >> p[i];  
}

// for(int i=1; i<=n; i++)
// cout << p[i]<< endl;

int total_length = 0;
int total_revenue = 0;

int student_claimed_revenue = 0;
int length = 0;

cin >> student_claimed_revenue;
do{
cin >> length;
if(length > 0)
{
total_length += length;
total_revenue += p[length];
}
}while(length >0);

//cout << total_length << endl;
//cout << total_revenue << endl;
  
int optimal_revenue;
cin >> optimal_revenue;

if (student_claimed_revenue != total_revenue || total_revenue != optimal_revenue)
cout << 0 << endl;

// Free allocated space
delete[] p;

return 1;
}

Dynamic Programming: Rod Cutting Description In this assignment you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem (chapter 15.) In the Rod Cutting problem, you are given an integer n 1, along with a sequence of positive prices, pi, p2, ...Pa, where pi is the market price of rod of length i. The goal is to figure out a best way of cutting the given rod of length n to generate the maximum revenue. You can assume that the given prices pi, p2, Pa are all integers. Input The input has the following format. The input starts with n. Then, pi.p2.Pa follow one per each line. Output In the first line, output the maximu revenue (r), followed by an enter key. In the second line, sequentially output the length of each piece in your optimal cutting, and output 1 followed by a space key; separate two adjacent numbers by a space key. Examples of input and Input output 10 Outpuf 18 1 6-1 The following is the output with white characters shown 18 (enter) 1 (space)6(space)-1(enter) Alternatively, the second line can be replaced with "61-1, "2 23-1, "2 3 2 -1", or "3 2 2 -1". That is, any sequence of piece lengths giving the maximum revenue will be considered to be correct.

Explanation / Answer

#include<iostream>
#include<climits>
using namespace std;

int rodCutting(int n, int value[])
{
int total[n+1]; // array to store the total revenue
total[0]=0;
//total[i]=maximum attainable revenue of rod of size i
for(int i=1;i<=n;i++) // finding the result for rod of size i
{
total[i]=INT_MIN;

//try to cut the rod of length i into various values of j
//and select the one which gives the maximum value
for(int j=0;j<i;j++)
{
total[i]=max(total[i],value[j]+total[i-(j+1)]);
}
}
return total[n];
}

int main()
{
int n;
cin>>n;
cout << endl ;
int value[n];
for(int i=0;i<n;i++) //Enter the values of pieces of rod of all size
cin>>value[i];
cout<<rodCutting(n,value); //Maximum obtainable value by cutting up the rod in many pieces

cout<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.