12.背包问题
我们有n种物品，物品j的重量为wj，价格为pj。
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。
# 图12-2 Item类
In [7]: class Item(object):
...: def __init__(self, n, v, w):
...: self.name = n
...: self.value = v
...: self.weight = w
...: def getName(self):
...: return self.name
...: def getValue(self):
...: return self.value
...: def getWeight(self):
...: return self.weight
...: def __str__(self):
...: result = '<' + self.name + ', ' + str(self.value)\
...: + ', ' + str(self.weight) + '>'
...: return result
...:
In [8]: def value(item):
...: return item.getValue()
...:
In [9]: def weightInverse(item):
...: return 1.0/item.getWeight()
...:
In [10]: def density(item):
...: return item.getValue()/item.getWeight()
...:
# 图12-3 贪婪算法的实现
In [11]: def greedy(items, maxWeight, keyFunction):
...: """假设Items是列表， maxWeight >= 0
...: keyFunctions将物品元素映射为数值"""
...: itemsCopy = sorted(items, key=keyFunction, reverse = True)
...: result = []
...: totalValue, totalWeight = 0.0, 0.0
...: for i in range(len(itemsCopy)):
...: if (totalWeight + itemsCopy[i].getWeight()) <= maxWeight:
...: result.append(itemsCopy[i])
...: totalWeight += itemsCopy[i].getWeight()
...: totalValue += itemsCopy[i].getValue()
...: return (result, totalValue)
...:
# 图12-4 使用贪婪算法选择物品
In [12]: def buildItems():
...: names = ['clock','painting','radio','vase','book','computer']
...: values = [175,90,20,50,10,200]
...: weights = [10,9,4,2,1,20]
...: Items = []
...: for i in range(len(values)):
...: Items.append(Item(names[i], values[i], weights[i]))
...: return Items
...:
In [13]: def testGreedy(items, maxWeight, keyFunction):
...: taken, val = greedy(items, maxWeight, keyFunction)
...: print('Total value of items taken is', val)
...: for item in taken:
...: print(' ', item)
...:
In [14]: def testGreedys(maxWeight = 20):
...: items = buildItems()
...: print('Use greedy by value to fill knapsack of size', maxWeight)
...: testGreedy(items, maxWeight, value)
...: print('\nUse greedy by weight to fill knapsack of size',
...: maxWeight)
...: testGreedy(items, maxWeight, weightInverse)
...: print('\nUse greedy by density to fill knapsack of size',
...: maxWeight)
...: testGreedy(items, maxWeight, density)
...:
In [15]: testGreedys()
Use greedy by value to fill knapsack of size 20
Total value of items taken is 200.0
<computer, 200, 20>
Use greedy by weight to fill knapsack of size 20
Total value of items taken is 170.0
<book, 10, 1>
<vase, 50, 2>
<radio, 20, 4>
<painting, 90, 9>
Use greedy by density to fill knapsack of size 20
Total value of items taken is 255.0
<vase, 50, 2>
<clock, 175, 10>
<book, 10, 1>
<radio, 20, 4>
其中函数getBinaryRep()和genPowerset()是在9.3.6 指数复杂度首次出现
In [22]: def getBinaryRep(n, numDigits):
...: """假设n和numDigits为非负整数
...: 返回一个长度为numDigits的字符串，为n的二进制表
...: 示"""
...: result = ''
...: while n > 0:
...: result = str(n%2) + result
...: n = n//2
...: if len(result) > numDigits:
...: raise ValueError('not enough digits')
...: for i in range(numDigits - len(result)):
...: result = '0' + result
...: return result
In [23]: def genPowerset(L):
...: """假设L是列表
...: 返回一个列表，包含L中元素所有可能的集合。例如，
...: 如果
...: L=[1, 2]，则返回的列表包含元素[1]、 [2]和[1,
...: 2]"""
...: powerset = []
...: for i in range(0, 2**len(L)):
...: binStr = getBinaryRep(i, len(L))
...: subset = []
...: for j in range(len(L)):
...: if binStr[j] == '1':
...: subset.append(L[j])
...: powerset.append(subset)
...: return powerset
...:
# 图12-5 0/1背包问题的暴力最优解
In [24]:
...: def chooseBest(pset, maxWeight, getVal, getWeight):
...: bestVal = 0.0
...: bestSet = None
...: for items in pset:
...: itemsVal = 0.0
...: itemsWeight = 0.0
...: for item in items:
...: itemsVal += getVal(item)
...: itemsWeight += getWeight(item)
...: if itemsWeight <= maxWeight and itemsVal > bestVal:
...: bestVal = itemsVal
...: bestSet = items
...: return (bestSet, bestVal)
...:
...: def testBest(maxWeight = 20):
...: items = buildItems()
...: pset = genPowerset(items)
...: taken, val = chooseBest(pset, maxWeight, Item.getValue,
...: Item.getWeight)
...: print('Total value of items taken is', val)
...: for item in taken:
...: print(item)
In [25]: testBest()
Total value of items taken is 275.0
<clock, 175, 10>
<painting, 90, 9>
<book, 10, 1>
12.2 图的最优化问题
# 图12-7 节点和边
In [49]: class Node(object):
...: def __init__(self, name):
...: """假设name是字符串"""
...: self.name = name
...: def getName(self):
...: return self.name
...: def __str__(self):
...: return self.name
...:
...: class Edge(object):
...: def __init__(self, src, dest):
...: """假设src和dest是节点"""
...: self.src = src
...: self.dest = dest
...: def getSource(self):
...: return self.src
...: def getDestination(self):
...: return self.dest
...: def __str__(self):
...: return self.src.getName() + '->' + self.dest.getName()
...:
...: class WeightedEdge(Edge):
...: def __init__(self, src, dest, weight = 1.0):
...: """假设src和dest是节点， weight是个数值"""
...: self.src = src
...: self.dest = dest
...: self.weight = weight
...: def getWeight(self):
...: return self.weight
...: def __str__(self):
...: return self.src.getName() + '->(' + str(self.weight) + ')'\
...: + self.dest.getName()
...:
# 图12-8 Graph类和Digraph类
In [50]: class Digraph(object):
...: #nodes是图中节点的列表
...: #edges是一个字典，将每个节点映射到其子节点列表
...: def __init__(self):
...: self.nodes = []
...: self.edges = {}
...: def addNode(self, node):
...: if node in self.nodes:
...: raise ValueError('Duplicate node')
...: else:
...: self.nodes.append(node)
...: self.edges[node] = []
...: def addEdge(self, edge):
...: src = edge.getSource()
...: dest = edge.getDestination()
...: if not (src in self.nodes and dest in self.nodes):
...: raise ValueError('Node not in graph')
...: self.edges[src].append(dest)
...: def childrenOf(self, node):
...: return self.edges[node]
...: def hasNode(self, node):
...: return node in self.nodes
...: def __str__(self):
...: result = ''
...: for src in self.nodes:
...: for dest in self.edges[src]:
...: result = result + src.getName() + '->'\
...: + dest.getName() + '\n'
...: return result[:-1] #omit final newline
...:
...: class Graph(Digraph):
...: def addEdge(self, edge):
...: Digraph.addEdge(self, edge)
...: rev = Edge(edge.getDestination(), edge.getSource())
...: Digraph.addEdge(self, rev)
...:
# 图12-9 最短路径的深度优先搜索算法
In [51]: def printPath(path):
...: """假设path是节点列表"""
...: result = ''
...: for i in range(len(path)):
...: result = result + str(path[i])
...: if i != len(path) - 1:
...: result = result + '->'
...: return result
...:
...: def DFS(graph, start, end, path, shortest, toPrint = False):
...: """假设graph是无向图； start和end是节点；
...: path和shortest是节点列表
...: 返回graph中从start到end的最短路径。 """
...: path = path + [start]
...: if toPrint:
...: print('Current DFS path:', printPath(path))
...: if start == end:
...: return path
...: for node in graph.childrenOf(start):
...: if node not in path: #avoid cycles
...: if shortest == None or len(path) < len(shortest):
...: newPath = DFS(graph, node, end, path, shortest,
...: toPrint)
...: if newPath != None:
...: shortest = newPath
...: return shortest
...:
...: def shortestPath(graph, start, end, toPrint = False):
...: """假设graph是无向图； start和end是节点
...: 返回graph中从start到end的最短路径。 """
...: return DFS(graph, start, end, [], None, toPrint)
...:
In [52]: def testSP():
...: nodes = []
...: for name in range(6):
...: nodes.append(Node(str(name)))
...: g = Digraph()
...: for n in nodes:
...: g.addNode(n)
...: g.addEdge(Edge(nodes[0],nodes[1]))
...: g.addEdge(Edge(nodes[1],nodes[2]))
...: g.addEdge(Edge(nodes[2],nodes[3]))
...: g.addEdge(Edge(nodes[2],nodes[4]))
...: g.addEdge(Edge(nodes[3],nodes[4]))
...: g.addEdge(Edge(nodes[3],nodes[5]))
...: g.addEdge(Edge(nodes[0],nodes[2]))
...: g.addEdge(Edge(nodes[1],nodes[0]))
...: g.addEdge(Edge(nodes[3],nodes[1]))
...: g.addEdge(Edge(nodes[4],nodes[0]))
...: sp = shortestPath(g, nodes[0],nodes[5],toPrint = True)
...: print('Shortest path is',printPath(sp))
...:
In [53]: testSP()
Current DFS path: 0
Current DFS path: 0->1
Current DFS path: 0->1->2
Current DFS path: 0->1->2->3
Current DFS path: 0->1->2->3->4
Current DFS path: 0->1->2->3->5
Current DFS path: 0->1->2->4
Current DFS path: 0->2
Current DFS path: 0->2->3
Current DFS path: 0->2->3->4
Current DFS path: 0->2->3->5
Current DFS path: 0->2->3->1
Current DFS path: 0->2->4
Shortest path is 0->2->3->5
丰一禾 2018/08/20 15:43:40
一、学习安排（8月16日-8月20日）
1.主要学习视频Week6
链接（[图片上传失败...(image-8c50b5-1534751046074)]
http://www.xuetangx.com/courses/MITx/6_00_2x/2014_T2/courseware/d39541ec36564a88af34d319a2f16bd7/）
2.参考书第十二章--背包与图的最优化问题
二、作业上传事项
1.此次作业内容包括几个方面：
（a）背包问题理解
（b）图最优化问题理解
（c）动态规划的理解
(提交形式，是以“汇报”形式汇报给助教（李凯旋），对于作业敷衍的直接视为下车)
2.作业提交日期
作业规定在8月20日24点之前，大家把握好时间，且8月21日晚上，助教会公布没有交作业者并令其下车；
@所有人
网友评论