脚本宝典收集整理的这篇文章主要介绍了201971010110-高杨 实验二 软件工程项目 《0-1背包问题》,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
项目 | 内容 |
---|---|
班级博客链接 | https://edu.cnblogs.com/campus/xbsf/2019nwnucs |
作业要求 | https://edu.cnblogs.com/campus/xbsf/2019nwnucs/homework/12527 |
实验目的与要求 | (1)掌握软件项目个人开发流程。 (2)掌握Github发布软件项目的操作方法。 |
这个作业在哪些方面帮助我实现学习目标 | (1)复习上学期的算法知识。 (2)了解Github发布软件项目的此操作方法。 (3)学习掌握PSP流程。 |
Github仓库链接地址 | https://github.com/2082993296/0-1- |
评论链接 | 评论内容 |
---|---|
https://www.cnblogs.com/1810067010LB/p/15969385.html | 博主所写内容简洁明了,期待博主的下一篇文章。 |
https://www.cnblogs.com/zrx04/p/15954327.html#5031316 | 博主内容充实详细,期待未来看到更多的佳作出自博主之手。 |
https://www.cnblogs.com/cyx6155729/p/15954318.html#5031315 | 博客内容充实详细,可以看出作者认真负责的态度,希望未来可以看到作者的更多佳作。 |
背包问题(Knapsack Problem,KP)是NP Complete问题,也是一个经典的组合优化问题,有着广泛而重要的应用背景。{0-1}背包问题({0-1 }Knapsack Problem,{0-1}KP)是最基本的KP问题形式,它的一般描述为:从若干具有价值系数与重量系数的物品(或项)中,选择若干个装入一个具有载重限制的背包,如何选择才能使装入物品的重量系数之和在不超过背包载重前提下价值系数之和达到最大? {0-1}KP数据集是研究{0-1}背包问题时,用于评测和观察设计算法性能的标准数据集;动态规划算法、回溯算法是求解{0-1}背包问题的经典算法。查阅相关资料,设计一个采用贪心算法、动态规划算法、回溯算法求解{0-1}背包问题的程序,程序基本功能要求如下:
PSP | 任务内容 | 计划完成时间 | 实际完成时间 |
---|---|---|---|
Planning | 计划 | 6 | 10 |
Estimate | 估计这个这个任务需要多少时间,并规划大致工作步骤 | 6 | 10 |
Development | 开发 | 600 | 860 |
Analysis | 需求分析(包括学习新技术) | 10 | 10 |
Design Spec | 生成设计文档 | 5 | 8 |
Design Review | 设计复审 | 10 | 15 |
Coding Standard | 代码规范 | 10 | 12 |
Design | 具体设计 | 20 | 30 |
Coding | 具体编码 | 600 | 650 |
Code Review | 代码复审 | 25 | 30 |
Text | 测试 | 160 | 140 |
Reporting | 报告 | 60 | 80 |
Test Report | 测试报告 | 20 | 40 |
Size Measurement | 计算工作量 | 10 | 20 |
Postmortem & Process Improvement Plan | 事后总结,并提出过程改进计划 | 20 | 30 |
def GreedyAlgo(item, C, idex):
number = len(item)
status = [0] * number
total_weight = 0
total_value = 0
for i in range(number):
if item[idex[i],0] <= C:
total_weight += item[idex[i],0]
total_value += item[idex[i],1]
status[idex[i]] = 1
C -= item[idex[i],0]
else:
continue
return total_weight, total_value, status
def Bag(n, W, V, C):
C = int(C)
n = int(n)
w = W.split(',')
w = [int(i) for i in w]
v = V.split(',')
v = [int(i) for i in v]
bagTable = [[0 for j in range(C + 1)] for i in range(n + 1)]
for key_n in range(1,len(bagTable)):
for key_c in range(1,len(bagTable[key_n])):
if w[key_n-1] > key_c:
bagTable[key_n][key_c] = bagTable[key_n-1][key_c]
else:
value1 = bagTable[key_n-1][key_c-w[key_n-1]] + v[key_n-1]
value2 = bagTable[key_n-1][key_c]
bagTable[key_n][key_c] = max(value1,value2)
def backtrack(i):
global bestV,curW,curV,x,bestx
if i>=n:
if bestV<curV:
bestV=curV
bestx=x[:]
else:
if curW+w[i]<=c:
x[i]=True
curW+=w[i]
curV+=v[i]
backtrack(i+1)
curW-=w[i]
curV-=v[i]
x[i]=False
backtrack(i+1)
以上是脚本宝典为你收集整理的201971010110-高杨 实验二 软件工程项目 《0-1背包问题》全部内容,希望文章能够帮你解决201971010110-高杨 实验二 软件工程项目 《0-1背包问题》所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。