Which of the following problems is NOT solved using dynamic programming? 0/1 knapsack problem Matrix chain multiplication problem Edit distance problem  Fractional knapsack problem

The problem that is NOT solved using dynamic programming is the Fractional knapsack problem.

Here's why:

1. 0/1 Knapsack Problem: This problem can be solved using dynamic programming because it has both optimal substructure and overlapping subproblems properties. In this problem, we are given a set of items, each with a weight and a value, and we need to determine the maximum value we can get if we can carry a total weight of W in our knapsack.

2. Matrix Chain Multiplication Problem: This problem can also be solved using dynamic programming. It is about finding the most efficient way to multiply a given sequence of matrices. The problem is not as simple as it seems, because the order in which the matrices are multiplied can significantly impact the number of simple arithmetic operations needed to perform the multiplication.

3. Edit Distance Problem: This problem can be solved using dynamic programming as well. It is about finding the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into another.

4. Fractional Knapsack Problem: This problem is different from the 0/1 Knapsack problem because it allows to take fractions of items, instead of making a binary (0/1) choice for each item. The Fractional Knapsack Problem can be solved using a greedy strategy, not dynamic programming. The greedy strategy involves taking the item with the highest value/weight ratio first, then the item with the next highest ratio, and so on, until the knapsack is full or there are no more items.