Problems 1 though 3

Suppose we have a knapsack that can hold at most 7 pounds. The table below lists the weight and value of four items: item weight 2 pounds 3 pounds 4 pounds 5 pounds value $3.00 $2.00 $4.00 $1.00 1. Use dynamic programming to solve the 0-1 knapsack problem and determine what items we should pack in the knapsack to achieve the maximum total value of packed items. Show your work. 2. Now assume we can pack fractions of the items. Use a greedy algorithm to solve this fractional knapsack problem (i.e., maximizing the total value of packed items). Show your work. 3. Suppose that in a 0-1 knapsack problem, the order of the items when sorted by increasing weight is the same as their order when sorted by decreasing value. Give an efficient algorithm to find an optimal solution to this variant of the knapsack problem, and argue that your algorithm is correct. Suppose we have a knapsack that can hold at most 7 pounds. The table below lists the weight and value of four items: item weight 2 pounds 3 pounds 4 pounds 5 pounds value $3.00 $2.00 $4.00 $1.00 1. Use dynamic programming to solve the 0-1 knapsack problem and determine what items we should pack in the knapsack to achieve the maximum total value of packed items. Show your work. 2. Now assume we can pack fractions of the items. Use a greedy algorithm to solve this fractional knapsack problem (i.e., maximizing the total value of packed items). Show your work. 3. Suppose that in a 0-1 knapsack problem, the order of the items when sorted by increasing weight is the same as their order when sorted by decreasing value. Give an efficient algorithm to find an optimal solution to this variant of the knapsack problem, and argue that your algorithm is correct