NP完全问题
什么是NP完全问题？
NP完全问题(NP-C问题)，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。
NP完全问题的简单定义是，几乎不可能编写出算法快速处理的问题。（比如集合覆盖问题，旅行商问题）
那么，如何去识别一个问题是不是NP完全问题？通常可以一些特点：
- 元素较多时，算法速度会显著降低速度
- 涉及“所有组合”的问题通常是NP完全问题
- 无法将问题分成小问题，必须考虑各种各样的可能情况。
- 如果涉及序列、集合并且难以解决，可能是NP完全问题
- 假如可以转换为旅行商问题或集合覆盖问题，那肯定是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
可以看出算法：
- 获取上一行同列商品的价格
- 获取当前行商品的价格+剩余空间可放置价格
- 对以上两者进行比较，取其大者
现在开始使用代码来实现：
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
与预期结果一样，可以更改几组测试用例进行测试。
注意
动态规划很强大，但是局限在与：每个子问题都必须是离散的，即相互之间不存在依赖。
要设计出动态规划解决方案可能很难，每种动态规划解决方案都涉及网格。
关于如何绘制网格，需要注意：
- 单元格中的值是什么？
- 如何将这些问题划分为子问题
- 网格的坐标轴是什么？
扫一扫，关注公众号
网友评论