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

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

相关推荐

不愿透露姓名的神秘牛友
01-07 20:45
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 17:00
点赞 评论 收藏
分享
2024-12-18 19:49
南京师范大学 Java
点赞 评论 收藏
分享
01-06 23:47
门头沟学院 前端工程师
点赞 评论 收藏
分享
01-06 20:50
北京信息科技大学 测试工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

招聘动态

查看更多

太平洋寿险科技赋能中心

2025校园招聘

全站热榜

正在热议
# 职场高情商速成班 #
2707次浏览 60人参与
# 职场吐槽大会 #
110740次浏览 909人参与
# 被同事甩锅了怎么办 #
13999次浏览 88人参与
# 怎么评价今年的华为 #
11172次浏览 85人参与
# 25届秋招总结 #
837756次浏览 8473人参与
# 机械制造薪资爆料 #
1154519次浏览 9432人参与
# 查收我的offer竞争力报告 #
98133次浏览 686人参与
# 实习生活中那些难忘的瞬间 #
8685次浏览 138人参与
# 大学最后一个寒假，我想…… #
6152次浏览 93人参与
# 寒假躺平还是提前实习 #
121638次浏览 1030人参与
# 双非本科求职如何逆袭 #
740018次浏览 7870人参与
# 我的实习求职记录 #
6512566次浏览 86375人参与
# 如果可以选，你最想去哪家公司 #
1346115次浏览 16704人参与
# 那些拿到大厂offer的简历长啥样 #
175199次浏览 2792人参与
# 今年过年，你可以休息几天？ #
4458次浏览 45人参与
# 测测你的职业性格 #
29798次浏览 289人参与
# 对未来的工作有什么期待 #
16800次浏览 176人参与
# 上班后，你最大的变化是什么？ #
21279次浏览 254人参与
# 实习，投递多份简历没人回复怎么办 #
2661818次浏览 36350人参与
# 数据人offer决赛圈怎么选 #
142538次浏览 1624人参与
牛客网
牛客企业服务