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
Output a table that show the cube of the numbers 1-15<br> (C++)
Rainbow [258]

Answer:

The c++ program to display cube of numbers from 1 to 15 is given below.

#include <iostream>

using namespace std;

int main() {    

   // variables declared and initialized  

   int num = 15, k, cube;    

   cout << " Cubes of numbers from 1 to 15 are shown below " << endl;    

   for( k = 1; k <= num; k++ )

   {

       // cube is calculated for each value of k and displayed

       cube = k * k * k ;

       cout << " \t " << cube << endl;

   }

return 0;

}

 

OUTPUT

Cubes of numbers from 1 to 15 are shown below  

  1

  8

  27

  64

  125

  216

  343

  512

  729

  1000

  1331

  1728

  2197

  2744

  3375

Explanation:

The variables are declared and initialized for loop, cube and for condition in the loop – k, cube, num respectively.

Inside for loop which executes over k, beginning from 1 to 15, cube of each value of k is calculated and displayed. The loop executes 15 times. Hence, cube for numbers from 1 to 15 is displayed after it is calculated.

   for( k = 1; k <= num; k++ )

   {

      cube = k * k * k ;

       cout << " \t " << cube << endl;

   }

In the first execution of the loop, k is initialized to 1 and variable cube contains cube of 1. Hence, 1 is displayed on the screen.

In the second execution, k is incremented by 1 and holds the value 2. The variable cube contains cube of 2, which is calculated, and 8 gets displayed on the screen.

After each execution of the loop, value of k is incremented.

After 15 executions, value of k is incremented by 1 and k holds the value 16. This new value is greater than num. Hence, the loop terminates.

3 0
3 years ago
You are the senior nurse on the unit and you are orienting a new graduate LVN/LPN. One of the subjects you want to cover today i
Margarita [4]

Answer: D. Homans sign

Explanation:

Check for the severity of the swelling, monitor the flow of blood to the tissue, pulses equality, check for homans sign such as pain in the leg around the calve, the calve is meant to be of equal size and warmth. There should not be any reddish colouration or pains around the calve when there is ankle movement as this shows a negative sign of homans.

3 0
3 years ago
A colleague has included you on an email that is irrelevant to you, but it continues to come to your inbox because people are us
Law Incorporation [45]

on google there is a mute function with the 3 dots on the top and outlook has it in the same location but under the word of "ignore"

7 0
3 years ago
What is the portrait mode ?
Effectus [21]
On a camera portrait mode is when the camera is vertical.
7 0
3 years ago
Explain the levels of data model​
gregori [183]

Answer:

Data modeling occurs at three levels—physical, logical, and conceptual.

  • A physical model is a schema or framework for how data is physically stored in a database.

  • A conceptual model identifies the high-level, user view of data.

  • A logical data model sits between the physical and conceptual levels and allows for the logical representation of data to be separate from its physical storage.

4 0
3 years ago
Other questions:
  • What is a browser? Give one example
    8·2 answers
  • Rob Janoff believes that technology should not be used too
    11·1 answer
  • Which evaluation factor will be most important when choosing technology for the company
    5·1 answer
  • What items do you keep in a data base
    5·1 answer
  • Discuss briefly general-purpose graphicsprimitives that contain 2D graphics library.
    15·1 answer
  • / Looks up author of selected books
    15·1 answer
  • How to make a harmonic mean algorithm in bash Linux?
    15·1 answer
  • This is your code.
    9·1 answer
  • What is the decimal value for the jump control?
    12·1 answer
  • 6
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!