Quiz 4 - Dynamic Programming and Backtrackin

Question 1

Given two integer arrays to represent weights and profits of ’N’ items, find a subset of these items that will give us maximum profit such that their cumulative weight is not more than a given number ‘C’.

Best technique to solve this problem is?

• Divide and Conquer
• Dynamic Programming
• Brute Force
• Backtracking

Answer 1

• Dynamic Programming

Question 2

To find the optimal solution for 0-1 knapsack, what would be dimensions of the extra array that we would need? The knapsack has a capacity of W, and there are total of n items. Assume we are using the approach that was discussed in the exploration.

Answer 2

Array[W+1][n+1]

Question 3

We are given an array of numbers and we are asked to find an optimal solution to maximize the sum of numbers (i.e continuous subsequence that has maximum sum). if the order of the input numbers were altered or if we use a different algorithm, we will always end up with the same combination of numbers as answer.

Answer 3

False

Question 4

Backtracking is used to solve which of the problems:

• Any numerical problems
• To find all possible solutions
• Optimal solution problems
• Problems that have sub-problems similar to divide and conquer

Answer 4

• To find all possible solutions

Question 5

What is the correct recurrence formula for the unbound knapsack problem that was discussed in the exploration?

Consider the weight of the items w[1..n], value of the items v[1..n]

• F(x) = max{ F[x-vi] + wi }
• F(x) = max{ F[x-wi] + vi }
• F(x,i) = max{ vi + F[x-wi , i-1] , F[x , i -1] }
• F(x,v) = max{ F[x-wi] + vi }

Answer 5

• F(x) = max{ F[x-wi] + vi }

Question 6

In the o-1 knapsack recurrence formula f(x,i) = max{ vi + f[x-wi , i-1] , f[x , i -1] }

The first part vi + f[x-wi , i-1] represents :
[ Select ]

The second part f[x , i -1] represents:
[ Select ]

Answer 6

adding the ith item to the knapsack

not adding the ith item to the knapsack