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
Rufina [12.5K]
3 years ago
10

You are given a list of n positive integers a1, a2, . . . an and a positive integer t. Use dynamic programming to design an algo

rithm that examines whether a subset of these n numbers add up to exactly t, under the constraint that you use each ai at most once. If there is a solution, your program should output the subset of selected numbers. Recurrence Relation (and base cases)
Computers and Technology
1 answer:
Anna11 [10]3 years ago
6 0

Answer:

See explaination for the program code

Explanation:

The code below

Pseudo-code:

//each item ai is used at most once

isSubsetSum(A[],n,t)//takes array of items of size n, and sum t

{

boolean subset[n+1][t+1];//creating a boolean mtraix

for i=1 to n+1

subset[i][1] = true; //initially setting all first column values as true

for i = 2 to t+1

subset[1][i] = false; //initialy setting all first row values as false

for i=2 to n

{

for j=2 to t

{

if(j<A[i-1])

subset[i][j] = subset[i-1][j];

if (j >= A[i-1])

subset[i][j] = subset[i-1][j] ||

subset[i - 1][j-set[i-1]];

}

}

//returns true if there is a subset with given sum t

//other wise returns false

return subset[n][t];

}

Recurrence relation:

T(n) =T(n-1)+ t//here t is runtime of inner loop, and innner loop will run n times

T(1)=1

solving recurrence:

T(n)=T(n-1)+t

T(n)=T(n-2)+t+t

T(n)=T(n-2)+2t

T(n)=T(n-3)+3t

,,

,

T(n)=T(n-n-1)+(n-1)t

T(n)=T(1)+(n-1)t

T(n)=1+(n-1)t = O(nt)

//so complexity is :O(nt)//where n is number of element, t is given sum

You might be interested in
Why do most programmers indent the conditionally executed statements in a decision structure?
Digiron [165]
It visually groups the statements that belong together, and allows you to quickly see the flow of a program by looking at the indents.
7 0
4 years ago
Describe the layout of an article on Wikipedia​
GuDViN [60]

An article with a table of contents block and an image near the start, then several sections

Sample article layout (click on image for larger view)

This guide presents the typical layout of Wikipedia articles, including the sections an article usually has, ordering of sections, and formatting styles for various elements of an article. For advice on the use of wiki markup, see Help:Editing; for guidance on writing style, see Manual of Style.

Contents

1 Order of article elements

2 Body sections

2.1 Headings and sections

2.2 Names and orders for section headings

2.3 Section templates and summary style

2.4 Paragraphs

3 Standard appendices and footers

3.1 Headings

3.2 Works or publications

3.3 "See also" section

3.4 Notes and references

3.5 Further reading

3.6 External links

3.6.1 Links to sister projects

3.7 Navigation templates

4 Specialized layout

5 Formatting

5.1 Images

5.2 Horizontal rule

5.3 Collapsible content

6 See also

7 Notes

8 References

A simple article should have, at least, (a) a lead section and (b) references. The following list includes additional standardized sections in an article. A complete article need not have all, or even most, of these elements.

The same article, with the central left highlighted: it contains just text in sections.

Body sections appear after the lead and table of contents (click on image for larger view).

Articles longer than a stub are generally divided into sections, and sections over a certain length are generally divided into paragraphs; these divisions enhance the readability of the article. The names and orders of section headings are often determined by the relevant WikiProject, although articles should still follow good organizational and writing principles regarding sections and paragraphs.

5 0
3 years ago
If you feel that an OSHA inspection is needed to get hazards corrected at your workplace, which is your best option?
KATRIN_1 [288]
Most likely bring it to your managers attention and and have him contact an OSHA employee.
4 0
4 years ago
How do productivity programs most benefit the way we work and live?
finlep [7]

Answer:

They provide us with ways to communicate, display, and work with information more quickly and accurately.

Explanation:

Productivity programs helps in the provision of information and they also help in increasing productivity by making work less stressful and unambiguous. Examples of productivity programs include design programs and spreadsheet tools.

These programs also create an avenue for providing us with ways to communicate, display and work with information more quickly and accurately.

6 0
4 years ago
Fill in the sentences with the correct terms.
ololo11 [35]
<h2>[+] Hello ! [+]</h2>

Answer:

<em>Cells provide data to another cell. </em>

<em>Cells rely on the value of another cell. </em>

Explanation:

  • I hope this helped
  • Tell me if it's wrong
  • Thanks for your time
  • Brainliest is always appreciated!!
  • Have a wonderful and blessed day :D
5 0
3 years ago
Read 2 more answers
Other questions:
  • The outstanding disk requests are for tracks 6,10,4,20,36,8, and 40 in that order. Assume that the seek time speed is 5 msec/tra
    14·1 answer
  • Identify four basic data manipulations performed on a relational database using sql
    7·1 answer
  • Your computer is taking longer than usual to open files and you notice that your hard drive light stays on longer than usual. wh
    5·2 answers
  • Yesterday you installed a new game on your computer. When you ran the computer, you noticed that the application was running ver
    15·1 answer
  • Does anyone know what type of Honda this is and the year of it lol this isn’t school related
    10·1 answer
  • PHP server scripts are surrounded by delimiters, which? *
    5·1 answer
  • HTML question please help
    5·1 answer
  • ....................
    5·1 answer
  • WRITE A PROGRAM TO CALCULATE SIMPLE INTEREST
    12·1 answer
  • When conducting memory and recall tests, some people make an effort to normalize memories by not reporting extreme cases. this l
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!