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 might you want to save a downloaded file to your computer first instead of running it immediately?
sukhopar [10]

Answer:

Explanation:

Run: Choose Run when you only need the download once. Perhaps it’s a song or video you only plan to listen to or watch once. Another scenario might be an installation program that, when run, installs software on your machine in other, permanent locations. Once installed, you probably don’t need the installer again.

Save: When you want to keep whatever it is you’ve downloaded, choose Save. You can still run it, or whatever else you’d like to do with it, but you’ll need to do that yourself. You’ll also want to decide where, on your computer, to keep the file.

<em>Save and run: Use this option when you want to do both: save the file to a location you control, and then immediately run it. </em>

<em />

8 0
2 years ago
In what ways do you think the media should function in a democratic society?
insens350 [35]

Answer:

i think it should slow down

Explanation:

i think this because people are always on social media so they should put down their devices and interact with others and sometimes they are violent on their devices so it would be better if people did stay off their devices for a little bit.

7 0
3 years ago
13. Place where names, addresses and email information<br> is stored
yanalaym [24]

Answer in ur email

Explanation:

8 0
2 years ago
All spreadsheet formula should start with
inysia [295]
A formula in Excel will ALWAYS start with = then the function name like
=SUM(A1:A5)
5 0
3 years ago
¿ cuales son las características de revolución industrial?
Daniel [21]

Answer:

La producción industrial a gran escala, especialmente de alimentos. ... El desarrollo de nuevas industrias como la textil, la siderúrgica (metales) o la minera. La sustitución del hierro por el acero, un material más duro y resistente.

Espero que esto sirva!

7 0
3 years ago
Other questions:
  • Media messages are communicated through which of the following:
    8·2 answers
  • Which of the following would be considered a primary source of information?
    6·1 answer
  • As an improvement of the ATX form factor over AT, shorter wires made it easier to shield them and made them capable of handling
    6·1 answer
  • A simulation system is a technology that enables you to take over a customer’s screen, mouse, or other connected device in order
    13·1 answer
  • Which person would be the best fit for a career in the Information Technology field?
    6·2 answers
  • Do you think people accept poor quality in information technology projects and products in exchange for faster innovation? What
    5·1 answer
  • There are many commercially made household linens found in the?
    7·1 answer
  • Plz help Complete the sentence.
    11·2 answers
  • Your project will require a 7-day work week rather than the traditional 5-day. How can you adapt the software to this new schedu
    15·1 answer
  • Which generation computer supported GUI operating system?​
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!