Description
1) Suppose that you have an array A. A = {2, 3, -5, -8, 6, -1}. Propose a dynamic programming
algorithm that checks whether there is a subset with total sum of elements equal to zero. Your
algorithm should display the elements of each subset whenever it finds them. Implement your
algorithm with Python and explain it in your report file.
2) Suppose that you have a set of integers arranged in the form of a triangle like below. Your aim
is to find the smallest sum path from the triangle apex to its base through a sequence of
adjacent numbers. The sequence in the following example is shown by the circles. Design a
dynamic programming algorithm for this problem. Implement your algorithm with Python and
explain it in your report file.
3) Suppose that you have a knapsack problem. You are given N items of weights đ¤1, đ¤2,⌠đ¤n and
their values are đŁ1, đŁ2, âŚ, đŁn,respectively. The knapsack has capacity đ. Your goal is to find the
most valuable subset of the items that fit into the knapsack.
You can pick from each item as
many as you can. Design a dynamic programming algorithm and explain each step in your
report file. Implement your algorithm with Python and explain it in your report file. Apply your
algorithm with these values:
đ¤1 = 5, đ¤2 = 4, đ¤3 = 2; đŁ1 = 10, đŁ2 = 4, đŁ3 = 3; W=9.