Week 6 > Dynamic Programming > Knapsack

Question 1

What is the knapsack problem definition?

Answer 1

Question 2

1. What are the knapsack problem variations?
2. In which knapsack problem variation greedy algorithm does not work?

Answer 2

2. Gree does not work for discrete knapsack! will design a dynamic programming solution.

Question 3

Can you provide the solution of 1. w/o repeats; 2. with repeats?

Answer 3

Question 4

Answer 4

• Greedy Solution: $30 -> 6 kg and $14 -> 3 kgs
• Optimal Solution: $30 -> 6 kg and $16 -> 4 kgs
• Since the total value of greedy solution = $44 while the optimal solution is $46