算法学习－动态规划

最近发现自己在算法的方面真的是犹如小学生一般，跟公司的从一些更厉害学校毕业的人都不在一个水平面上，唉，觉得以前大学期间真心是一个学渣，虽然软件工程方面还可以，但是时候该补一补关于算法的相关知识了。

学习算法的同时，也顺带着学习python脚本语言。

动态规划

动态规划是通过组合子问题的解来解决整个问题的，通过将问题分解成多个相互不独立的子问题，例如0/1背包问题，对每个子问题求解一次，并将其结果保存到一张辅助表中，避免每次遇到各个子问题时再重新计算，动态规划通常用于解决最优化问题。

（1）全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 ；
（2）动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解 ；
（3）边界条件：即最简单的，可以直接得出的局部最优解。

有n件物品，第i件物品价值为v_i元，重量为w_i，假设v_i和w_i都为整数，希望带走的东西越值钱越好，但他的背包中之多只能装下W磅的东西，W为一整数。问题是应该带走哪几样东西？

0/1背包问题是一个典型的最优子结构的问题，只能采用动态规划来解决，不能采用贪心算法。

class Commodity:
    def __init__(self, value, weight):
        self.__value = value
        self.__weight = weight

    def get_value(self):
        return self.__value

    def get_weight(self):
        return self.__weight


if __name__ == '__main__':
    totalCount = 3
    bagCapacity = 50

    commodities = [Commodity(0, 0), Commodity(60, 10), Commodity(100, 20), Commodity(120, 30)]
    matrix = [[0 for i in range(bagCapacity + 1)] for i in range(totalCount + 1)]

    # initial set value = 0 when commodity count = 0
    for i in range(1, bagCapacity + 1):
        matrix[0][bagCapacity] = 0

    for i in range(1, totalCount + 1):
        # set max value = 0 when capacity = 0
        matrix[i][0] = 0
        for w in range(1, bagCapacity + 1):
            if ( commodities[i].get_weight() <= w):
                if (commodities[i].get_value() + matrix[i - 1][w - commodities[i].get_weight()] > matrix[i - 1][w]):
                    matrix[i][w] = commodities[i].get_value() + matrix[i - 1][w - commodities[i].get_weight()]
                else:
                    matrix[i][w] = matrix[i - 1][w]
            else:
                matrix[i][w] = matrix[i - 1][w]


    print "The max value matrix is : %s" % matrix

    remaining_space = bagCapacity
    # we should output selected commodity
    for i in range(totalCount, 0, -1):
        if(remaining_space >= commodities[i].get_weight()):
            if(matrix[i][remaining_space] - matrix[i-1][remaining_space-commodities[i].get_weight()] == commodities[i].get_value()):
                print "item %s selected" % i
                remaining_space -= commodities[i].get_weight()

 

首先，我们定义了一个Commodify类来描述物品的二维特性，价值和重量。

 

第一步，逐步建立局部最优解的状态矩阵，状态矩阵表示，在一定数量内的物品，一定范围的总重量范围内的最大价值是多少？

 

我们最简单的边界条件设置为，当有0个物品时，最大价值必定为0；当物品的总重量为0时，最大价值也必然为0；

 

第二步，当我们选定一个物品，如何判断是否应该加入最优解的结果中呢？首先判断这个物品是否大于局部最优解限定的重量，如果大于直接pass掉，使用上一步骤的局部最优解。

 

如果在限定的重量范围内，并且加上这个物品的要比不加这个物品的局部最优解要大，也就是说质量不变的情况下，能否用更多数量的物品达到更大价值，那么这是最新的最优解；否则仍然选择上一步骤的局部最优解，判断条件为：

if (commodities[i].get_value() + matrix[i - 1][w - commodities[i].get_weight()] > matrix[i - 1][w]):

 

最后，我们建立起这个矩阵，最后面的matrix[totalCount+1][bagCapacity+1]就是最终的最优解。

 

那么需要列出在此过程中，我们选择了哪些物品，从局部最优矩阵的结果入手，向前递推，如果遍历的这个物品的最优解减掉该物品的重量刚好差值为该物品的质量，那么证明刚才的最优解中选择了该物品。

 

if(matrix[i][remaining_space] - matrix[i-1][remaining_space-commodities[i].get_weight()] == commodities[i].get_value()):
                print "item %s selected" % i
                remaining_space -= commodities[i].get_weight()