“01背包问题”描述

​ 一个网站管理员，工作目标是在保证不被查水表的前提下尽可能吸引更多的流量。

​ 他拥有的资源类型、各自的猎奇度和危险程度如下：

​ 假设网站最高能承受的危险程度之和为18点，他该如何选择网站资源才能使得网站猎奇度最高？

解决思路

​ 01背包问题是动态规划算法的经典例题之一。解题思路如下：

​ 先从最后一个资源开始考虑，该管理员可以将“政治”挂在网站上，也可以不挂。为了决定挂不挂，他准备让手下甲和乙去做这么两件事：

• 甲去计算并向管理员报告：如果不挂“政治”，只考虑前四种资源，网站最高能达到的猎奇度加上之前已经挂上的资源的猎奇度（目前为0）是多少；

• 然后管理员判断了一下现有危险程度容量是否足够挂“政治”资源，如果不够，则不给乙布置任何任务。如果够，则让乙去计算挂上“政治”后，考虑前四种资源，网站剩余的（18-6=12点）危险程度容量能达到的最高猎奇度加上之前已经挂上的资源的猎奇度（目前只有”政治“）一共是多少。

​ 之后甲和乙模仿着管理员的思路，将自己的任务分成了类似的两个部分（挂“花边”还是不挂“花边”），分给了各自的两名手下去做。

​ 最后会有人接到的任务是：

• 不考虑任何资源，网站能达到的猎奇度（必为零）加上之前已经挂上的资源的猎奇度是多少？

• 挂上“动漫”资源，不考虑任何资源，网站剩余的危险程度能容纳的最高猎奇度（必定为0）加上之前已经挂上的资源的猎奇度一共是多少？

​ 这些人能够直接回答一个数字，而不用再将任务分给两个手下去做了。

​ 每一个管理者将手下报告的数字中取一个最大值报给上级，最终甲和乙将数字报告给网站管理员，管理员选择最大的数值即是网站能达到的最大猎奇度。

​ 为了知道最大猎奇度对应的挂了哪些资源，网站管理员只需判断甲和乙谁给的数字更大，如果甲更大说明没有挂“政治”，如果乙更大说明挂了。如果甲报的数字更大，则让甲看看两名手下谁报的数字更大，下面同理。如此可以得到该挂哪些资源。

​ 看完上面的思路，可能第一反应是用递归的方法实现代码，递归实现的代码我直接放到第三部分，下面想说说如何用迭代实现这个计算过程。

​ 迭代求解背包问题可以通过填一个表来实现，见表1。

​ 回想上面的解决思路，最先得到数据的是最底层的工作人员，最后得到数据的是网站管理者。因此我们在写代码时，应该考虑从上面表格的左上角开始填写，即上表中已经填好的0（可以理解为边界条件）。

​ 接着，从表格第三行的（3，3）元素开始填，应用之前的思想，先让一个手下计算不挂“动漫”网站最大猎奇度，这个手下得到的就应该是（2，3）元素的值0。然后他考虑网站剩余危险程度点数为1，不足以容纳“动漫”，所以只能取第一个手下返回的值，（3，3）填0。

​ 然后考虑（3，4），类似的，第一个手下得到的是（2，4）的值0，然后他发现可以挂“动漫”资源了，于是让另一名手下计算剩余的（2-2=0点）危险程度能使网站达到的最大猎奇度加上已经挂上的资源的猎奇度，这个手下得到的应该是（2，2）的值加上5，也就是5。最终取两名手下所报数字的最大值，也就是5，填入（3，4）中。

​ 以下同理。实现的代码放在第三部分。

代码实现（python）

​

import numpy

def choose(n,t,novelty,danger):
    """
    n 资源种类数量
    t 网站能承受的危险程度，threshold的首字母
    novelty 每种资源的猎奇度列表
    danger 每种资源的危险程度
    :return: 返回填好的决策表value，其中元素代表某种情况下网站最大猎奇度
    """

    # 初始化表格，所有数值置零
    value = numpy.zeros((n+1,t+1),dtype=numpy.int32)
    for i in range(1,n+1):
        for j in range(1,t+1):
            value[i][j] = value[i-1][j]  # 这是甲去做的工作，先假设它最大
            if j>danger[i-1]:   # 如果剩余危险程度点数足够挂第i个资源，给乙布置工作
                value[i][j] = max(value[i][j],value[i-1][j-danger[i-1]]+novelty[i-1])   # 取甲乙所得数字中较大那个
    return value


def show(n,t,danger,value):
    """
    查找挂在网站上的资源是哪些
    比较甲乙谁给的数字更高，得知某个资源是否选中
    :return: 返回n×t选择数组choice，元素值为1则代表该资源被选中
    """
    choice = [0 for i in range(n)]
    for i in range(n,0,-1):
        if value[i][t]>value[i-1][t]:
            choice[i-1]=1
            t -= danger[i-1]
    return choice

if __name__ == '__main__':
    n = 5   # 资源数量
    t = 18   # 总危险程度容量
    novelty = [5, 3, 8, 4, 10]   # 各种资源的猎奇度
    danger = [2, 1, 8, 5, 6]   # 各种资源的危险程度
    value = choose(n, t, novelty, danger)
    print("最大猎奇度为%d" % value[n][t])
    # print (*value, sep='\n')
    choice = show(n, t, danger, value)
    print("最优选择方案为：")
    for i in range(n):
        if choice[i]:
            print("第", i+1, "个")