背包问题

问题描述

假如有一个能装下4磅的背包，如何从下列商品列表中选择商品填充背包，使价值达到最大：

商品	重量	价值
吉他	1磅	1500
电脑	3磅	2000
音响	4磅	3000

动态规划

要解决背包问题，就需要用到动态规划。
动态规划先解决子问题，再逐步解决大问题。
对于背包问题，先解决小背包（子背包）问题，再逐步解决原来的问题。

每个动态规划算法都从一个网格开始，背包问题的网格如下：

商品\磅数	1	2	3	4
吉他
电脑
音响

行代表可以选择的商品，比如第二行表示本行可选择把电脑放到背包，但是第二行只能选择吉他和电脑。列代表背包的容量。

详细说明

接下来一步步填满表格。

填充第一行

第一行只能选择吉他，当背包是1磅的时候，吉他正好也是1磅，所以目前最大的价值就是把吉他放入背包，价值为1500：

商品\磅数	1	2	3	4
吉他	1500
电脑
音响

对于第一行的其他列来说，背包的空间虽然一直在增加，但是没有其他可选择的，所以价值都是1500：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑
音响

填充第二行

接下来第二行，背包是1磅和2磅的时候，电脑的大小是3磅，不能放入背包，所以还是只能选择吉他，所以价值仍然为1500：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑	1500	1500
音响

当背包大小增加到3磅的时候，这时候需要做出两种选择：放入电脑；不放入电脑。放入电脑的价值为2000，不放入电脑放入吉他价值为1500，所以我们选择值大的：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑	1500	1500	2000
音响

当背包增加到4磅的时候，我们仍然面临两个选择：放入电脑；不放入电脑。①放入电脑，我们发现还剩1磅，还可以放入吉他，所以价值为3500；②不放入电脑，只能选择吉他，价值为1500。所以我们选择放入电脑+吉他：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑	1500	1500	2000	3500
音响

填充第三行

接下来开始填充第三行，背包是1磅的时候，由于音响是4磅，所以放不进去，我们只能在电脑和吉他中做选择，其实就是第二行的情况，我们把上一行的数值填入即可：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑	1500	1500	2000	3500
音响	1500

对于第三行在背包为2磅和3磅的情况，跟1磅的时候一样，我们只能根据第二行的数值填入：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑	1500	1500	2000	3500
音响	1500	1500	2000

第三行在背包达到4磅的时候，我们面临两个选择：放入音响；不放入音响。①放入音响，正好占满背包，价值为3000；②不放入音响，其实就是第二行的情况，价值为3500。所以最大价值为3500：

商品\磅数	1	2	3	4
吉他	1500	1500	1500	1500
电脑	1500	1500	2000	3500
音响	1500	1500	2000	3500

公式

使用动态规划时，要么考虑拿走商品，要么考虑不拿，所以可以总结为：

公式

代码实现

在代码中，表格的初始化多了一行一列，这样就可以减少对边界值的判断。

values = {}
values['guitar'] = {}
values['guitar']['weight'] = 1
values['guitar']['value'] = 1500
values['PC'] = {}
values['PC']['weight'] = 3
values['PC']['value'] = 2000
values['audio'] = {}
values['audio']['weight'] = 4
values['audio']['value'] = 3000

total_value = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]


def find_max_value():
    row = 1
    max_value = 0
    for item in values:
        weight = values[item]['weight']
        value = values[item]['value']
        for j in range(1, len(total_value[row])):
            if weight <= j:
                total_value[row][j] = max(total_value[row-1][j],
                                          value+total_value[row-1][j-weight])
            else:
                total_value[row][j] = total_value[row-1][j]
            if total_value[row][j] > max_value:
                max_value = total_value[row][j]

        row += 1

    return max_value


print(find_max_value())

动态规划适合场景

• 生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
• 你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。
• 前面讨论了字符串的相似程度。编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
• 你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！