0/1 knapsack problem using branch and bound

To find upper bound of knapsack which method is used?

• Greedy method

• Backtracking

• Dynamic Programming

• None of the above

First step (in order to find upper bound) in solving 0/1 knapsack is

• Sort all items according to decreasing order of ratio of value per unit weight

• Sort all items according to increasing order of ratio of value per unit weight

• Add all profit

• None of the above

What is the profit and weight of dummy item?

• 0 0

• 1 1

• -1 -1

• 1 0

What is the upper bound of given knapsack?

• 50

• 55

• 57

• 60

What is the value (profit) of given knapsack when item 1 is considers (Node B)?

• 52

• 25

• 22

• 50

What is the upper bound of given knapsack when item 1 is not considers (Node C)?

• 40

• 45

• 47

• 50

What is the value (profit) of given knapsack when item 1 and item 2 are considers (Node D)?

• 52

• 50

• 55

• 57

What is the value (profit) of given knapsack when item 1 is considered and item 2 are not considers (Node E)?

• 22

• 25

• 40

• 45

What is the value (profit) of given knapsack when item 1, item 2 and item 3 is considers (Node F)?

• 62

• Since weights of all items exceeds knapsack capacity, we cant consider node F

• 60

• 50

What is the value (profit) of given knapsack when item 1, item 2 are considered and item 3 is not consider (Node G)?

• 52

• 55

• 50

• 57