01背包问题可不可以不用动态规划解
然而用动态规划解的目的就是得到最优解啊。
否则的话用贪心不就完了。
■网友
显然满足整数规划约束的解都是可以的，至于近似算法的证明……可能题主需要系统的找本书学一下？
顺便吐槽几个点：
NPC其实是一类判定性问题，如果你已经在求最优解了，可能用NPO来形容更合适一些动态规划不可能在多项式时间给出背包的最优解，请算一下表达背包的大小需要多少个bit事实上，可以基于动态规划设计一个背包的FPTAS—————好像应该给个算法再走——————
提供一个贪心近似算法，
所有物品按 收益/代价 排序，按顺序取到不能取为止取一个收益最大的物品在1、2之中选总收益更大的那个作为最终的结果。
这个算法在这类问题上算是比较经典的了，实践中情况2你也可以取到不能取为止
■网友
不想要最优解当然随便搞就好，不过好像解的质量没保证，比如某几个显然的贪心可以构造数据让解任意地烂。
■网友
建议搜索『整数规划』
■网友
爆搜法和贪心法也是解决01背包的思路，但都存在局限。
爆搜法解01背包举例：背包容量 m = 10，物品大小 A = ，物品价值 V =
爆搜解法：分别枚举每一个物体取或者不取，1代表取，0代表不取
爆搜算法的局限：
贪心法解01背包取价值最高：
m=2, A = , V = 贪心答案：3，正确答案：4取重量最轻 ：
m=2, A = , V = 贪心答案：2，正确答案：3取单位价值最高：
m=3, A = , V = 贪心答案：4，正确答案：5可以看到，所有的贪心都是错误的！！！
那么，动态规划如何解01背包呢？
举例1：
背包容量 m = 10 ，物品大小 A = ，物品价值 V = 。
使用数组来记录取前i个物品，在容量j的情况下能取的最大价值 ：
dp表示前i个物体，在容量j的情况下，能取到的最大价值
如果取第i个物体，价值为dp] + V (j-A\u0026gt;0)
如果不取第i个物体，价值为dp
状态转移：dp = max(dp] + V, dp)
实际上，除了01背包外，我们还需要掌握背包问题的另外2种的子问题——完全背包和多重背包问题，剩下一些都是这3种的变形以及组合。
如果你想把这个知识点学得更透彻，可以听一听《背包四讲》，基础知识和刷题都覆盖到了~
这门原价$199的课程，现在$1秒杀！
参与方式：
戳我免费试听后，添加九章Sunny微信jiuzhang15，回复【背包】+试听报名截图即可$1购买本课程。
参与条件：
九章新用户（未在九章购买过课程的都算新用户哦~）
■网友
可以啊，搜索也行。
■网友
应该从时间复杂度来分析吧，动态规划已经是效率较高的了。 目前线性规划的一些解法，例如对偶单纯形，里面一旦用到高斯消元法，时间复杂度都上O(n^3)了吧。n物品的个数。
■网友
跑线性规划，\u0026gt;0.5的取，否则不取，然后xjb调整下？
复杂度还不如背包吧
■网友
【01背包问题可不可以不用动态规划解】 挑战NPC！
推荐阅读
- 江苏■江苏交控坚持问题导向、瞄准职工需求——找准“病灶”当好“产改先行官”
- 贵州在建骨干水源工程达到465座有效解决工程性区域性缺水问题
- 四川眉山瓦屋山景区就游客投诉、停车难等问题公开道歉
- 杭州已整改城市道路无障碍环境问题12467处
- 互联网怎样解决“家政服务上门速度慢”的问题
- 中东问题|
- 中国网汽车|购车2个多月、仅行驶8000多公里 宝骏730遭遇7处问题
- |沛县深入开展教育领域突出问题专项整改
- 交换机，路由器经常性的死机咋办
- 微博目前已经支持文本，图片，位置分享，为啥没有语音和视频呢微博的pm肯定想过这两种微博形态，但迟迟不做的原因到底是啥。是语音和视频不符合产