《算法图解》笔记 iv

NP完全问题

什么是NP完全问题？

NP完全问题(NP-C问题)，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

NP完全问题的简单定义是，几乎不可能编写出算法快速处理的问题。（比如集合覆盖问题，旅行商问题）

那么，如何去识别一个问题是不是NP完全问题？通常可以一些特点：

1. 元素较多时，算法速度会显著降低速度
2. 涉及“所有组合”的问题通常是NP完全问题
3. 无法将问题分成小问题，必须考虑各种各样的可能情况。
4. 如果涉及序列、集合并且难以解决，可能是NP完全问题
5. 假如可以转换为旅行商问题或集合覆盖问题，那肯定是NP完全问题

动态规划

动态规划的工作原理是先解决子问题，然后逐步解决大问题。

小时候看过一档央视娱乐节目叫“购物街”，内容可以简单概括为：在有限的一辆购物车空间内，尽可能放置价格总和最高的商品。

这很有意思，假设每种商品的数量为1，同时也能知道各商品的价格，我们如何在最短的时间内，计算出需要放置的东西，以及最终的价格之和为多少？

第一种最简单的思路，将所有符合要求的排列组合列出，然后计算其价格总和，再进行对比。

这似乎是可以操作的，让我们用数字来估算一下：

商品数量	集合数量
3	8
4	16
5	32
32	40亿

可见在商品数量不是很多的时候，这种算法已经行不通了。

使用动态规划来解决问题

商品名称	价格	空间
手机	3000	1
平板	4000	3
电脑	8000	4

假设购物车的空间为4，我先假设一张商品表：

商品名称	价格	空间
手机	3000	1
平板	4000	3
电脑	8000	4

动态规划的问题是将大问题简化为子问题，那么在这个问题中，如何划分为子问题？减少商品类型和缩小购物车空间。

先构建一张表，行为新加入的商品，列为已使用的空间：

image

现在开始算法：

第一行只有手机可以挑选（而且手机数量为1），所以得到以下表格

image

第二行有手机和平板可以挑选：

image

可以看出算法：

1. 获取上一行同列商品的价格
2. 获取当前行商品的价格+剩余空间可放置价格
3. 对以上两者进行比较，取其大者

现在开始使用代码来实现：

def dp_func(bill,zone):
    #首先生成二维数组
    bill_list=list(bill.keys())
    array_row=len(bill)
    array_column=zone+1
    array=[[0]*array_column for i in range(array_row)]
    #开始判断
    for i in range(0,array_row):
        for j in range(1,array_column):
            previous=array[i-1][j]#上一行同列商品的价格
            current_goods_price=bill[bill_list[i]][0]#当前行商品的价格
            current_goods_zone=bill[bill_list[i]][1]#当前行商品的空间
            if j-current_goods_zone>=0:
                left_price = array[i - 1][j - current_goods_zone]  # 剩余空间可放置的商品价格
                if previous > current_goods_price + left_price:
                    array[i][j] = previous
                else:
                    array[i][j] = current_goods_price + left_price
            else:
                array[i][j] = previous
    return array

if __name__ == '__main__':
    test_bill={"手机":[3000,1],"平板":[4000,3],"电脑":[8000,4]}
    cart_zone=4
    print(dp_func(test_bill,cart_zone))

输出：

image

与预期结果一样，可以更改几组测试用例进行测试。

注意

动态规划很强大，但是局限在与：每个子问题都必须是离散的，即相互之间不存在依赖。

要设计出动态规划解决方案可能很难，每种动态规划解决方案都涉及网格。

关于如何绘制网格，需要注意：

1. 单元格中的值是什么？
2. 如何将这些问题划分为子问题
3. 网格的坐标轴是什么？

扫一扫，关注公众号