联系方式

  • 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

powerset.py. Name your file PowerSet.py

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%)?

4. Any other comments?

Note: ‘Debriefing’ section is intended to help us calibrate the assignments.


版权所有:编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。