若能证明容量有限的背包问题在多项式时间内解出，则所有背包都属于P
我在我的优化算法课程中发现了这个问题，整个问题是这样的：如果我们可以证明所有容量限制在100的背包问题都可以在多项式时间内解决，那么所有的背包问题都属于P。这句话是真的还是假的？辩解。
通过我的书和一些研究，我得出了这样的结论：首先，KP是一个NP完全问题。动态规划可以达到伪多项式时间，但还不够。如果荒谬地，我们可以证明容量限制在100的KP可以在多项式时间内求解，那么我们可以假定KP属于P。
共有1个答案
证明所有容量有限的背包问题都可以在多项式时间内求解，并不证明所有背包问题都在P中，如果一个问题在P中，则意味着它可以在多项式时间内求解。这意味着它可以在O(n^k)中求解，其中k是某个整数。大O是一个上界，这意味着，如果一个算法是O(n)，当n接近无穷大时，做这些算法所花费的时间永远不会超过n。通过证明n<100的所有问题都可以在多项式时间内求解，这就不能保证更大的n。因此，我们不能说有一个算法在O(n^k)中运行，因此在P中运行。
-
在讲座中，我们已经考虑了背包问题：有n个项的正权值为w1，..、wn和值v1，..vn和容量为W的背包。问题的可行解是使总重量不超过W的物品的子集。目标是找到一个最大可能总价值的可行解。对于权值均为正整数的情形，我们讨论了求解时间为O(nW)的背包问题的动态规划解法。 a）假设所有项目的权值都是正整数，而不是权值。项目的权值可以是任意的正实数。描述一个解决背包问题的动态规划算法，如果所有项目的值都
-
我有一个项目清单，每个项目都有一个价格--或者就背包问题而言，一个重量。可购买物品的数量只受预算的限制，所以只要总花费不超过某个常数，就有可能购买尽可能多的物品。我也有一个算法，它基于某些变量，告诉每一个项目的利润（即每一个项目的价值）。所以基本上，我有一个有界背包问题，额外的条件是每个物品中有一个以上适合背包。 我想在这些条件下使利润最大化。我知道没有一个有效的解决方案，但至少有一个可行的方案吗
-
主要内容：动态规划解决01背包问题,01背包问题的具体实现商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品。装哪些商品才能获得最大的收益呢？在限定条件内找到最佳的物品组合，这样的问题统称为背包问题。 根据限定的条件不同，背包问题还可以细分： 部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包； 0-1 背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品
-
本文向大家介绍小背包问题，包括了小背包问题的使用技巧和注意事项，需要的朋友参考一下 列出了物品列表，每件物品都有自己的值和重量。物品可以放在最大重量限制为W的背包中。问题是要找到小于或等于W的重量，并且值要最大化。 背包问题有两种。 0 – 1背包 小背包 对于0 – 1背包，不能将物品分成小块，对于小背包，可以将物品分成小块。 在这里，我们将讨论分数背包问题。 该算法的时间复杂度为O（n Log
-
主要内容：贪心算法解决部分背包问题在限定条件下，如何从众多物品中选出收益最高的几件物品，这样的问题就称为背包问题。 图 1 背包问题 举个简单的例子，商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品，选择哪些商品才能获得最大的收益呢？这个问题就属于背包问题，限定条件是背包的承重，最终目标是令背包中存放的物品的总收益最高。 根据不同的限定条件，背包问题还可以有更细致的划分： 0-1 背
-
问题 你面前摆放着 n 个珠宝（共 n 种，每种 1 个），已知珠宝 s_i 的价值是 v_i ，重量是 w_i 。给你一个背包，你可以自由挑选珠宝装到背包中，但背包可以装载的最大重量为 t 。求背包能够装载珠宝的最大价值 v 。 解法 设 f(i,j) 为背包中放入前 i 件物品，重量不大于 j 的最大价值，其中 i in [1,n] ， j in [0,t] 。有如下状态转移方程： f(i,j