1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
FromTheMoon [43]
3 years ago
10

Choose a problem that lends to an implementation that uses dynamic programming. Clearly state the problem and then provide high-

level pseudocode for the algorithm. Explain why this algorithm can benefit from dynamic programming. Try to choose an algorithm different from any already posted by one of your classmates.
Computers and Technology
1 answer:
Svetradugi [14.3K]3 years ago
8 0

Answer:

Explanation:

The maximum weighted independent collection of vertices in a linear chain graph is a straightforward algorithm whereby dynamic programming comes in handy.

Provided a linear chain graph G = (V, E, W), where V is a collection of vertices, E is a set of edges margins, and W is a weight feature function applied to each verex.  Our goal is to find an independent collection of vertices in a linear chain graph with the highest total weight of vertices in that set.

We'll use dynamic programming to do this, with L[k] being the full weighted independent collection of vertices spanning from vertex 1 \to vertex k.

If we add vertex k+1 at vertex k+1, we cannot include vertex k, and thus L[k+1] would either be equivalent to L[k] when vertex k+1 is not being used, or L[k+1] = L[k-1] + W[k+1] when vertex k+1 is included.

Thus, L[k+1] = max \{ L[k], \ L[k-1] + W[k+1] \}

As a result, the dynamic programming algorithm technique can be applied in the following way.

ALGO(V, W, n) // V is a linearly ordered series of n vertices with such a weight feature W

\text{1. L[0] = 0, L[1] = W[1], L[2] = max{W[1], W[2]} //Base cases} \\ \\ \text{2. For i = 3 to n:- \\} \\ \\\text{3........ if ( L[i-1] > L[i-2] + W[ i ] )} \\ \\ \text{4............Then L[ i ] = L[i-1]} \\ \\ \text{5.........else} \\ \\ \text{6................L[i] = L[i-2] + W[i] }\\ \\ \text{7. Return L[n] //our answer.}

As a result, using dynamic programming, we can resolve the problem in O(n) only.

This is an example of a time-saving dynamic programming application.

You might be interested in
how to write a function "void funct()" which will accept a string from the user as input and will then display the string backwa
Mariulka [41]

Answer:

#include <bits/stdc++.h>

using namespace std;

void funct(){

   string name;

   cout<<"enter the string: ";

   cin>>name;

   

    reverse(name.begin(), name.end());

    cout<<"The string is : "<<name<<endl;

   

}

int main()

{

   funct();

 

  return 0;

}

Explanation:

create the function funct() with return type void and declare the variable type string and print a message for asking to used enter the string.  

The string enter by user is store in the variable using cin instruction.

after that, we use a inbuilt function reverse() which takes two argument.

firs argument tell the starting point and second index tell the ending point. then, the reverse function reverse the string.

name.begin() it is a function which return the pointer of first character of string.

name.end()  it is a function which return the pointer of last character of the string.

finally, print the reverse string.

for calling the function, we have to create the main function and then call the function.

5 0
3 years ago
Which one of the following terms is defined as the material and surfaces upon which an artist works?
katrin [286]

Media is the surface or material that an artist works on


5 0
3 years ago
1.
saul85 [17]

Answer:

1. Speakers

2. Software

3. C.P.U

4. ROM

5. Hard drive

6. RAM

7 0
2 years ago
What are three consequences of a negative digital Trail​
Vladimir79 [104]

Answer:

The digital footprint that is had behind can have repercussions in every aspect of your adolescent's life, conceivably bringing about botched occupation chances, public sharing of individual data, destroyed connections

Explanation:

Digital trail what's left behind as you calmly peruse the web, post via web-based media or even sort into a visit administration. Regardless of whether you're mindful, you add to your advanced impression or profile every day when you sign onto the Internet. The sites you visit, the news posts you remark on, the remarks you leave via web-based media stages—every one of these things meet up to make a representation of your online life.  

The digital footprint that is had behind can have repercussions in every aspect of your adolescent's life, conceivably bringing about botched occupation chances, public sharing of individual data, destroyed connections — or, in what is likely more pertinent to them at this moment: Their folks discovering what they've been up to and along these lines being rebuffed.

8 0
3 years ago
What are at least three tips to taking photographs of insects? Why would following the tips help create better photographs?
Ber [7]

1) Use a good cam 2) Make sure you focus on it 3) Make sure you snap it at the right time....    I hope this helps!!!!!

7 0
3 years ago
Other questions:
  • What is an independent data mart?
    8·1 answer
  • Up to 10 people is a good guideline for the size of your study group.
    15·1 answer
  • Technician A says that high pressure in recycled refrigerant is only caused by air contamination. Technician B says that recycle
    15·1 answer
  • 15 points. Please give an actual answer and not some random thing. this is not just free points. Correct answer will receive bra
    12·2 answers
  • Which of the following statement is False? 1 point Context free language is the subset of context sensitive language Regular lan
    5·1 answer
  • Question 1(Multiple Choice Worth 5 points)
    9·1 answer
  • Modify the CountByFives application so that the user enters the value to count by. Start each new line after 10 values have been
    7·1 answer
  • Can someone follow my tt its c1ndy.dont.miss
    6·1 answer
  • Explain why you do not need expensive equipment to take pictures or record video?
    7·2 answers
  • How do you delete questions you asked?
    7·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!