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
The safest action to take if someone claiming to be from your banks calls you to ask for account information is to
aalyn [17]
<h2>Answer:</h2>

<u>The correct option is</u><u> (B) hang up and call back using the banks official phone number</u>

<h2>Explanation:</h2>

There are a lot of cases where people pretend to call from the banks where the receivers have the account. The caller tries to take the information from the receiver and pretends to be the bank official. If there is any doubt then the receiver should hang up the call and call back the official number of the bank to confirm that whether somebody has called from the bank to get the information.

8 0
3 years ago
Read 2 more answers
The larget social networking site to date is
maks197457 [2]
FB, I would guess.

Sincerely,

Xeno
3 0
3 years ago
Which of the following are some popular debugging techniques?
topjm [15]

Answer:

a fix any syntax bugs. I looked it up on the internet so you should be good good luck on your test

8 0
2 years ago
A(n) _____ converts the programming instructions written by programmers into a language that the computer understands and proces
qaws [65]

Answer: Translator

Explanation:

each instruction written by programmer in another language must be converted (translated) to machine language in order to process, because computer understand only machine language( 0 and 1). that is translator.

8 0
3 years ago
Plz answer all the questions :)
AURORKA [14]

Answer:

is there multiple choice or do i have to answer from my own words??

7 0
3 years ago
Other questions:
  • Easy question how the internet has impacted y’all life
    13·1 answer
  • How can you differentiate between standard and protocol? Write at least on example of each of these terminologies?
    12·1 answer
  • Which type of password would be considered secure
    13·2 answers
  • According to social penetration theory, the __________ dimension concerns the number of topics disclosed whereas the __________
    6·1 answer
  • Copyright applies to work at the time it was produced, written, and developed. True or False?
    10·2 answers
  • Who do you guys ship lol bit with?
    14·2 answers
  • By what decade were books readily available to the public across the United States and Europe?
    7·1 answer
  • A good machine should have the mechanical advantage of......?​
    7·1 answer
  • The action of entering data into your computer. This can be text typed in a word processing document, keywords entered in a sear
    8·1 answer
  • When can screentips be useful? when finding a tab when looking for a command when pinning the ribbon when using a command.
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!