Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

can you help revised this python code to solve this problem using dynamic programming? I got different value! it supposes to be 260 for the

can you help revised this python code to solve this problem using dynamic programming?
I got different value! it supposes to be 260 for the inout!
and there are other input/output should the code get the correct solution as shown.
image text in transcribed
image text in transcribed
image text in transcribed
memory limit per test: 256 megabytes input: standard input output: standard output To further enthance your programming skills, you enrolled in an online CS program from UCR. In the program, you can enroll in whichever courses you want, and pay your tuition just for the courses you enroll in. The price for each course is different. We use pi to denote the price of course i. There are two different types of courses, main courses, and discussion courses. The discussion courses are always associated with exactly one main course. A main course can have 0,1 , or 2 discussions. If you want to register for a discussion course, you have to register for its main course at the same time. However, if you want to register for a main course, you may choose to attend each of its discussions or not (either way is fine). For example, If you enroll in a course with two discussions. you can choose to enroll in neither discussions, or any one of them, or both of them. Before you choose the courses, you looked at the reviews of the courses online. Each of the courses has a rating ri between 1 to 5 stars. 5 stars is the highest, Combining the price and rating, the yalue of each course is the product of rating and price (ripi for course i). Your budget for taking this online program is m dollars. You want to know, based on the rules above, what is the highest total value (ripi) you can get from the courses you enroll in. Input The first line contains two integers, m(1m32000), which is the budget, and n(1n60). which is the number of courses available. The next n lines each contains three integers pi,ri,ci(1in), describing a course. pi is the price of this course, ri is the rating of the course. ci describes if this course is a main course or discussion. If ci=0, this course is a main course. If ci=1, this course is a discussion, and its main course is course ci. The labels of the courses start from 1. Output There is only one integer in the output, which is the highest value you can get. The output is guaranteed to be within 2105. def solve (m,n, courses): dp=[[0](m+1) for in range (n+1)] for i in range (1,n+1) : p,r,c= courses [i1] for j in range (1,m+1) : if c=0 : dp[i][j]=max(dp[i1][j],dp[i1][jp]+rp) else: dp[i][j]=max(dp[i1][j],dp[i1][jp]+rp,dp[c1][jp]+rp) return dp[n][m] Note The best solution of the first sample is to choose courses 4,5 (discussion of course 4) and 6

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

More Books

Students also viewed these Databases questions

Question

What do Adlerians mean by encouragement?

Answered: 1 week ago