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
How should work be allocated to the team in a Scrum project?
Mkey [24]

Answer:

In a Scrum project, the work or the tasks are not allotted specifically. The Scrum Master is not allowed to assign tasks to the team members under any circumstance. Once the client provides the details regarding their requirements in detail, the tasks are distributed based on the expertise and skills of the employee.

Explanation:

4 0
3 years ago
Florida revoked __________ drivers licenses for DUI in a one-year period from 2009 to 2010.
rusak2 [61]
<h2>Answer:</h2>

<u>Florida revoked </u><u>36872 </u><u>drivers licenses for DUI in a one-year period from 2009 to 2010.</u>

<h2>Explanation:</h2>

The word DUI means Driver under influence. This influence is usually under alcohol or any other drug. A DUI arrest means when someone is caught driving a vehicle while under the influence of alcohol or drugs. One can still get a DWI if one is pulled over for some reason other than erratic driving.  120 days minimum mandatory jail and up to one year jail maximum may be imposed for DUI but it depends on state to state laws.

6 0
3 years ago
Read 2 more answers
How much will your assignment be docked if you turn it in late?
o-na [289]
We don’t know ms.Fredrick, you’re on your own here
7 0
3 years ago
Read 2 more answers
what is happening when humans control the breeeding of living things to favor certain desired features
sweet-ann [11.9K]
Selective Breeding is happening.
6 0
3 years ago
Imagine you accidently mistype the URL for your bank and you are redirected to a fake website that collects your information. Wh
fgiga [73]

Answer:

Financial identity theft

Explanation:

Financial identity theft is a fraudulent act that involves accessing someone's personal information without their consent or approval for fraudulent financial gain.

A typical financial identity theft is someone stealing your credit card information such as pin, cvv, etc. to make other financial transactions without your knowledge.

7 0
3 years ago
Other questions:
  • What shooting position is commonly used when hunting with a shotgun?
    14·2 answers
  • Templates allow for the quick creation of _____.
    7·1 answer
  • Ar count = 10;
    13·1 answer
  • The keyboard and the mouse____ parts of a computer ​
    8·1 answer
  • Knowing what you know about today’s video games, imagine what it would look like if you had to create a modern-day version of Sp
    6·1 answer
  • I WILL GIVE BRAINLIEST TO WHO ANSWERS FIRST AND CORRECTLY.
    12·1 answer
  • Apex
    5·2 answers
  • What is the importance of effectiveness in communication?
    14·1 answer
  • • Comments are blank which can be blank entered into documents
    5·1 answer
  • Convert the following denary numbers into binary using 8-bit register:
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!