knapsack问题之动态规划
问题描述
你有一个负重量为capacity的背包，摆在你面前的是一堆宝物，宝物有重量weight和价值value，你要在你的背包中装下宝物将它们占为己有，因此你希望背包中的宝物负重量不超过capacity，同时背包中的宝物的价值value尽可能的大。
输入：
4 11
8 4
10 5
15 8
4 3
第一行4 11表示宝物数量item_count为4，背包负重量capacity为11
接下来为item_count行，每行第一个元素是该宝物的价值value，第二个元素是该宝物的重量weight。
问题建模
x[i]=1表示选中宝物i,x[i]=0表示不选宝物i；w[i]和v[i]分别表示第i个宝物的重量和价值。K指背包负重量capacity。
解决方法
这个问题我们可以先用递归法理一下思路：
1）假设我们已经知道如何解决“j-1个宝物，capacity为k(k为0，...，K)”这个子问题，即：
O(k, j-1) for all k in 0...K
2）我们想要解出O(k,j)，即添加一个宝物进去
3）如果w[j] < k，那么存在两种情况：1.不选择第j个宝物，那么解为O(k,j-1)；2.选择第j个宝物，那么解为v[j] + O(k-w[j], j-1)
总结伪代码如下：
O(k, 0) = 0 for all k
O(k, j) = max(O(k, j-1), v[j] + O(k-w[j], j-1)) if w[j] <= k
O(k, j) = O(k, j-1) otherwise
但是实际中这个自顶向下的递归非常耗时，因为它有大量重复计算，我们需要将它改造成自底向上的算法，我们可以通过一个二维表来实现。
假设我们要解决以下具体问题：
下面我们要构造一个二维数组，列向是capacity（0~K）,横向是所有的宝物，我们根据上文中的伪代码在数组中填入数值，下面图中的箭头出发位置的值应该是多少？在w[j] <= k的情况下，我们有两种选择：
1）如果我们不选择第三个宝物，那么背包中宝物的价值和是水平箭头所指的值6（即O(k,j-1)）；
2）如果我们选择第三个宝物，那么背包中宝物的价值和是斜箭头所指的值5加上第三个宝物的价值3即8（v[j] + O(k-w[j], j-1)）。
两种选择中选最大值，所以是8。
以此类推，我们可以算完整个表格，在表格的右下角就是我们想要的值。
但是我们如何得出具体的选择方案呢？很简单，我们从右下角往回走，如果它跟它左边格子的值相等，意味着我们没有选择这个宝物（图中11 == 11，没有选择宝物3）；如果它跟它左边格子的值不想等，意味着我们选择了这个宝物，再往回走的时候就应该减去这个宝物的价值value（图中11 - 6 = 5）。
以此类推，我们可以知道我们选择了宝物1和宝物2。
memory
我们回想一下这个算法的空间占用情况，发现它计算了一个capacity * item_count大小的表格，item_count是跟输入规模有关的，但是capacity却不是。这个算法的内存占用大小竟然要受一个输入参数值的大小的影响！！假设capacity大小为100W，而item_count只有100，我们就需要计算一个1000000 * 100的表格，也就是说在capacity非常大的情况下这个算法会非常占内存。
show me the code
#!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy as np
from collections import namedtuple
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])))
# a trivial greedy algorithm for filling the knapsack
# it takes items in-order until the knapsack is full
value = 0
weight = 0
taken = [0]*len(items)
############################## sulution #################################
A = np.zeros((capacity+1, item_count+1), dtype=np.int)
for j in range(1,item_count+1):
for i in range(1, capacity+1):
if items[j-1].weight > i:
A[i][j] = A[i][j-1]
else:
A[i][j] = max(A[i][j-1], A[i-items[j-1].weight][j-1] + items[j-1].value)
value = A[capacity][item_count]
j = item_count
i = capacity
while j!=0:
if A[i][j] != A[i][j-1]:
taken[j-1] = 1
i = i - items[j-1].weight
j -= 1
# prepare the solution in the specified output format
output_data = str(value) + ' ' + str(0) + '\n'
output_data += ' '.join(map(str, taken))
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)'
