What is the time complexity of the brute force algorithm used to solve the Knapsack problem?

Which of the following is a correct time complexity to solve the 0/1 knapsack problem where n and w represents the number of items and capacity of knapsack respectively?

A

O(n)

B

O(w)

C

O(nw)

D

O(n+w)

Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?

A

O(n2)

B

O(n3)

C

O(nlogn)

D

O(2n)

What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?

A

O(1)

B

O(n)

C

O(n2)

D

O(2n)

What is the time complexity of the brute force algorithm used to solve the balanced partition problem?

A

O(1)

B

O(n)

C

O(n2)

D

O(2n)

In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?

A

O(n)

B

O(n2)

C

O(n!)

D

O(2n)

A superincreasing knapsack problem is ____ to solve than a jumbled knapsack.

A

Easier

B

Tougher

C

Shorter

D

Lengthier

What is the time complexity of the brute force algorithm used to find the longest common subsequence?

A

O(n)

B

O(n2)

C

O(n3)

D

O(2n)

What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?

A

O(1)

B

O(2n)

C

O(n)

D

O(n2)

A 0-1 knapsack problem has four items and knapsack capacity 11. The weight and profit of each item is given in below table. Pi (Rs.) 50 30 32 27 W = 11 Wi (Kg) 5 6 4 3 Which of the following greedy strategy gives the maximum profit?

A

Lightest item first

B

Largest profit first

C

Largest profit per unit weight first

D

Heaviest item first

Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?

A

In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible

B

Both are the same

C

0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming

D

In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

What is the time complexity of the brute force algorithm used to solve the Knapsack problem?

Related Questions