Answer: D
0/1
Knapsack problem:
Given a set of n objects
which have each have a value vi and a weight wi.
The objective of the
0/1 Knapsack problem is to find a subset of objects such that the total value
is maximized, and the sum of weights of the objects does not exceed a given
threshold W.
An important condition
here is that one can either take the entire object or leave it. It is not
possible to take a fraction of the object.
Possible
Method 1: Look at all possible combinations of objects,
calculate their total weight, and if the total weight is less than the
threshold, to calculate the total value. This approach is known as the Brute
Force. Although this approach would give us the solution, it is of exponential time complexity. Hence, we
look at the other possible methods.
Possible
Method 2: Use the Dynamic Programming approach
to solve this problem. Although this method is far more efficient than the
Brute Force method, it does not work in scenarios where the item weights are
non-integer values.
Possible
Method 3: Backtracking can
also be used to solve this problem. By exploring all possible branches until
the solution is invalid, then going back a step and exploring other
possibilities. This method also has exponential
time complexity.
Possible
Method 4: Since this is a combinatorial problem, once can use
the Branch and Bound method to solve this problem. Thing to be noted is that the Branch and
Bound method is for minimization problems.
Answer: D
0/1
Knapsack problem:
Given a set of n objects
which have each have a value vi and a weight wi.
The objective of the
0/1 Knapsack problem is to find a subset of objects such that the total value
is maximized, and the sum of weights of the objects does not exceed a given
threshold W.
An important condition
here is that one can either take the entire object or leave it. It is not
possible to take a fraction of the object.
Possible
Method 1: Look at all possible combinations of objects,
calculate their total weight, and if the total weight is less than the
threshold, to calculate the total value. This approach is known as the Brute
Force. Although this approach would give us the solution, it is of exponential time complexity. Hence, we
look at the other possible methods.
Possible
Method 2: Use the Dynamic Programming approach
to solve this problem. Although this method is far more efficient than the
Brute Force method, it does not work in scenarios where the item weights are
non-integer values.
Possible
Method 3: Backtracking can
also be used to solve this problem. By exploring all possible branches until
the solution is invalid, then going back a step and exploring other
possibilities. This method also has exponential
time complexity.
Possible
Method 4: Since this is a combinatorial problem, once can use
the Branch and Bound method to solve this problem. Thing to be noted is that the Branch and
Bound method is for minimization problems.