0/1背包问题是np难度问题的,为什么呀?

0/1背包问题是np难度问题的,为什么呀?它不是可以用动态规划在多项式时间求解吗?😂#笔试题目#
全部评论
背包问题是伪多项式时间,因为其优化函数依赖于背包的大小,而且加法本身耗时也不能视作多项式内,而是指数时间。实际上,可以通过将二进制加法转换为逻辑判断,将01背包规约到3sat问题,这是一个np完全问题
点赞 回复 分享
发布于 2019-06-05 18:21

相关推荐

offerboyyyy:之前看到降温完收到offer了的呢佬,可以签保底等
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务