联系方式

• QQ：99515681
• 邮箱：99515681@qq.com
• 工作时间：8:00-23:00
• 微信：codinghelp

您当前位置：首页 >> Python编程Python编程

日期：2021-04-25 05:17

Assignment: Dynamic Programming & Backtracking

1. Solve Dynamic Programming Problem and find its optimal solution.

Given a set of numbers, return a subset of non-consecutive numbers that would have the

maximum sum.

For example: Input: [7,2,5,8,6]

Output: [7,5,6] (This will have sum of 18)

Note: The numbers can include negative numbers as well.

a. Write the recurrence formula to solve this problem using dynamic programming

b. Write the pseudocode to solve the problem using dynamic Programming technique.

c. Implement the solution of this problem using dynamic Programming. Name your

function max_independent_set(nums). Name your file MaxSet.py

d. What is the time complexity of your implementation?

2. Implement a backtracking algorithm

a. Write the implementation to solve the powerset problem. Name your function

b. What is the time complexity of your implementation?

Debriefing (required!): --------------------------

Report:

1. Approximately how many hours did you spend on this assignment?

2. Would you rate it as easy, moderate, or difficult?

3. How deeply do you feel you understand the material it covers (0%–100%)?