knapsack问题之relaxation, branch and bound
转载请注明出处：BackNode
我们接着上回（传送门：动态规划）继续分析knapsack问题。
问题描述
你有一个负重量为capacity的背包，摆在你面前的是一堆宝物，宝物有重量weight和价值value，你要在你的背包中装下宝物将它们占为己有，因此你希望背包中的宝物负重量不超过capacity，同时背包中的宝物的价值value尽可能的大。
输入：
第一行4 11表示宝物数量item_count为4，背包负重量capacity为11
接下来为item_count行，每行第一个元素是该宝物的价值value，第二个元素是该宝物的重量weight。
数学模型
解决方法
对于每一个宝物，我们面临着两个选择：1.把它放进背包;2.不把它放进背包。我们可以用一棵二叉树来表示所有可能的情况，左节点表示把宝物放进背包，右节点表示不把宝物放进背包：
遍历完这颗完整二叉树仍然需要非常大的计算量，我们需要考虑给这棵树修建一下，找一个园丁来给它剪剪枝（pruning）。对于每一个节点，我们预估一下它能取得的最高价值（estimate），如果一个节点的estimate比当前取得的最高价值（best_value）还要低，那么我们就没有必要继续遍历这个节点的子节点了，因为反正它不可能取得比它的estimate还要高的价值，这样我们就从这个节点砍下一刀，剪去了它的子节点。那么问题来了，我们如何算出estimate值呢？让我们将注意力转移到这个问题的限制条件上：背包的负重量capacity。假设我们有一个非常神奇的背包，它的负重量无穷大，那我们可以在根节点的时候算出它的estimate值：所有宝物价值之和。我们不可能取得比这更大的值了，这样我们就通过relaxation得到了bound。下面我们看看详细过程：
每一个节点有三个属性：value,room,estimate。value表示该节点目前取得的宝物价值，room表示该节点背包剩余空间。
1）当节点空间小于0时，表明这个方案是行不通的。
2）当节点estimate小于目前找到的方案中取得的最高宝物价值（best_value）时，表明它的子节点没有必要再遍历了。
3）当遍历到叶子节点时，如果它的value比best_value要高，并且它的空间room不小于0，那么我们就找到了一个更好的方案，将这个方案标记为目前找到的最佳方案（value=best_value）。
这样，当我们遍历完成之后，一定能找到一个最佳方案。
relax something else
回想一下，上面的relax步骤中，我们一下将背包的负重量调到了无穷大，我们是不是太大方了？导致最后剪掉的枝干并不是很多，让我们试试有没有其他地方可以relax的。假设我们的宝物不是完整不可分割的，而是可以像巧克力一样可以掰开的。这样我们就可以按照价值重量比从高到低选取宝物，选到装不下的时候，将宝物掰开放进去使背包刚好装满，那样我们一定就带走了最有价值的宝物。按照这个方法计算estimate，我们可以剪掉更多的枝干。
注意：在每次计算节点estimate值的时候，每次我们都要根据剩下宝物的信息计算estimate。
show me the code
#!/usr/bin/python
# -*- coding: utf-8 -*-
import copy
from collections import namedtuple
from collections import deque
class Stack(object):
def __init__(self):
self.buffer = deque()
def push(self, node):
self.buffer.append(node)
def pop(self):
return self.buffer.pop()
def __len__(self):
return len(self.buffer)
class Node(object):
def __init__(self, depth, value, room, estimate, take):
self.depth = depth
self.value = value
self.room = room
self.estimate = estimate
self.take = take
Item = namedtuple("Item", ['index', 'value', 'weight'])
def solve_it(input_data):
# Modify this code to run your optimization algorithm
# parse the input
lines = input_data.split('\n')
firstLine = lines[0].split()
item_count = int(firstLine[0])
capacity = int(firstLine[1])
items = []
for i in range(1, item_count+1):
line = lines[i]
parts = line.split()
items.append(Item(i-1, int(parts[0]), int(parts[1])))
################################ solution 1 #######################################
stack = Stack()
sorted_items = sorted(items, key=lambda tup: float(tup.value) / tup.weight, reverse=True)
def calEstimate(room, depth):
estimate = 0.0
weight = 0.0
for item in sorted_items[depth::]:
if weight + item.weight <= room:
estimate += item.value
weight += item.weight
else:
estimate += item.value * (float(room) - weight) / item.weight
break
return estimate
max_estimate = calEstimate(capacity, 0)
best_value = 0
best_taken = [0] * (item_count+1)
current_taken = [0] * (item_count+1)
root = Node(0, 0, capacity, max_estimate, 0)
stack.push(root)
while len(stack) > 0:
current = stack.pop()
if current.room < 0 or current.estimate < best_value:
continue
elif current.depth < item_count:
left_node = Node(
current.depth + 1,
current.value + sorted_items[current.depth].value,
current.room - sorted_items[current.depth].weight,
current.estimate,
1)
right_node = Node(
current.depth + 1,
current.value,
current.room,
current.value + calEstimate(current.room, current.depth+1),
0)
stack.push(right_node)
stack.push(left_node)
if current.depth != 0:
current_taken[sorted_items[current.depth-1].index] = current.take
elif current.depth == item_count:
if current.value > best_value and current.room >= 0:
best_value = current.value
current_taken[sorted_items[current.depth-1].index] = current.take
best_taken = copy.deepcopy(current_taken)
############################################################################
output_data = str(best_value) + ' ' + str(1) + '\n'
output_data += ' '.join(map(str, best_taken[0:-1]))
return output_data
import sys
if __name__ == '__main__':
if len(sys.argv) > 1:
file_location = sys.argv[1].strip()
input_data_file = open(file_location, 'r')
input_data = ''.join(input_data_file.readlines())
input_data_file.close()
print solve_it(input_data)
else:
print 'This test requires an input file. Please select one from the data directory. (i.e. python solver.py ./data/ks_4_0)'
