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
If an M/M/1 queue in a server has task arrivals at a rate of 30 per second and serves at a rate of 50 per second, how many tasks
Scorpion4ik [409]

The answer & explanation for this question is given in the attachment below.

6 0
3 years ago
Can you anyone please help me​
Yuliya22 [10]

Answer:

Option C I think

3 0
2 years ago
Create a stored procedure sp_Q1 that takes two country names like 'Japan' or 'USA'as two inputs and returns two independent sets
Zigmanuir [339]

Answer:

Check the explanation

Explanation:

CREATE PROCEDURE sp_Q1

<u><em>"at"</em></u>country1 NVARCHAR(15),

<u><em>"at"</em></u>country2 NVARCHAR(15)

AS

BEGIN

  BEGIN

      SELECT SupplierID, CompanyName, Phone, Country FROM suppliers

      where Country in (<u><em>"at"</em></u>country1,<u><em>"at"</em></u>country2)

     

  SELECT ProductID, ProductName, UnitPrice, SupplierID FROM Products

      where SupplierID in(

      SELECT SupplierID FROM suppliers

      where Country in (<u><em>"at"</em></u>country1,<u><em>"at"</em></u>country2)) ORDER BY SupplierID

  END

END

GO

-- Testing script.

DECLARE <u><em>"at"</em></u>RC int

DECLARE <u><em>"at"</em></u>country1 nvarchar(15)

DECLARE <u><em>"at"</em></u>country2 nvarchar(15)

-- Set parameter values here.

set <u><em>"at"</em></u>country1='UK'

set <u><em>"at"</em></u>country2='Canada'

EXECUTE <u><em>"at"</em></u>RC = [dbo].[sp_Q1]

<u><em>"at"</em></u>country1

,<u><em>"at"</em></u>country2

GO

Kindly check the attached images below to see how it looks like on a code editor.

7 0
3 years ago
To ease giving access to network resources for employees, you decide there must be an easier way than granting users individual
scoundrel [369]

Answer

The intranet security model

Explanation:

This is an enterprise system that processes user information for security  and access authentication. It prevents unauthorized users, who are not part of the network resources from capturing these information.

The intranet security model is an efficient security procedure that incorporates web security  access control in keeping information safe over the intranet. It is also useful in encryption and decryption techniques.

4 0
3 years ago
Which of the following is true for an API?
navik [9.2K]

Answer:

c

Explanation:

4 0
3 years ago
Other questions:
  • Imagine that the following two lines of code are placed inside a
    11·1 answer
  • Which guideline should you use when downloading software from the Internet?
    15·1 answer
  • Lisa has a section of her document that she would like to include in the index. Which option should Lisa choose?
    12·1 answer
  • How many bytes does a common processor require to represent an integer?
    7·1 answer
  • do you think that some people have difficulty talking to others face to face because of how prevalent texting is today
    15·2 answers
  • REPORT THIS USER. HE'S SHOWING HIS YK WHAT TO EVERYONE INCLUDING ME. HIS ACCOUNT PROFILE IS IN THE PICTURE BELOW
    14·1 answer
  • How can a user access the Mailbox Cleanup tools?
    11·2 answers
  • A location in memory which stores a value, the value can change as the program is running is
    12·1 answer
  • NEED ANS ASAP THANK YOU
    14·1 answer
  • Your development team is planning to host a development environment on the cloud. This consists of EC2 and RDS instances. This e
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!