背包问题可以通过动态规划解决，为什么还说背包问题是NPC的？
或者说这两个背包问题不是同一个问题？
按投票排序
0-1背包的复杂度是O(nW)，n是物品数量，W是背包最大承载重量。W的值是根据输入规模指数变化的（注意这里的输入规模是二进制位，比如10位，W最大值就为1023；11位，W最大值就为2047）。为什么要关心二进制位？因为在计算机底层，输入规模就是二进制位的大小。所以O(nW)相对输入规模就是指数级的。
如果你真的想搞清楚这个问题的话，你需要先看很多资料。首先，你需要看看NPC问题是怎么定义的，尤其是如何判断时间复杂度是否多项式时间。(注重看怎么encoding，然后时间复杂度n是哪个n)其实，背包问题的解的时间复杂度，跟总价值是多项式关系的，这是伪多项式时间复杂度，因为总价值不是输入的那个n。这个我一时间解释不好，建议看看NPC问题的定义，和背包问题用动态规划解决后，时间复杂度的式子。
大家都回答得差不多了，我就来写得正式一点吧。假设输入是。表示背包大小，表示每个物体的大小，表示每个物体的价值。输入规模（输入的二进制编码长度）动态规划算法的时间复杂度为 。然而并不能够表示为，其中为任意多项式。所以动态规划算法不是多项式时间复杂度的，所以也不能证明背包问题是P问题。至于为什么背包问题是NPC问题，大家可以查看其他资料，我相信问题并不是想问这个。PS：为什么我们讨论算法时间复杂度时，要用输入的二进制编码表示其输入规模？当我们讨论一个算法的时间复杂度时，是在说算法运行时间与其输入规模的关系。用正式一点的语言来说，一个算法就是一台确定性图灵机M，M对于长度为N的输入串，能够在某个函数T(N)的时间内输出结果，这个函数T(N)就是这台图灵机的时间复杂度。一个问题实例的规模就是指它被编码到图灵机的输入带上的长度。可以证明的是，用任何有限的字符集来编码，T(N)本质上都不会变，只是会乘上某个常数因子。所以通常我们用输入的二进制编码长度来表示输入规模。PPS：实际上我觉得说动态规划算法时间复杂度为时暗含了都是小于某个常数的，这样一些对于数的操作才能在常数时间内完成。PPPS：这个问题下看到了好几位我校大神...ORZ
背包的复杂度受物品总价值影响，总价值与输入规模不存在多项式关系，输入规模极小也可以达到很大的复杂度。所说是对的。————————————————————————————————————————下面是题主原问题的答案……背包貌似不适用普通的线性规划，应该视为整数规划，可以认为是一个0-1规划模型。而整数规划或0-1规划似乎没有多项式解法
背包DP的时间复杂度是指数级的，不是多项式级。动态规划是一类算法，这类算法的复杂度可以是线性的，也可以是指数级。
NPC不意味着没有解法，只是解法不是多项式复杂度度的。。。高于多项式复杂度的 所以是NPC啊
已有帐号？
无法登录？
社交帐号登录求解0-1背包问题的动态规划法分析
0前言现实生活中,0-1背包问题[1]可被表述成许多工业场合的应用,如资本预算、货物装载和存储分配等问题,因此对该问题的研究具有很重要的现实意义和实际价值。该问题可描述为:n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包的容量为W。如何选取物品装入背包,使背包中所装入的物品的总价值最大?另外,在选择装入背包的物品时,对于物品i只有两种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入物品i的一部分。假设xi表示物品i被装入背包的情况,当xi=0时,表示物品没有被装入背包;当xi=1时,表示物品被装入背包。因此该问题被称为0-1背包问题。根据问题的描述,设计出如下的约束条件和目标函数。约束条件:∑ni=1wixi?Wxi∈｛0,1｝,(1?i?n{)(1)目标函数:max∑ni=1vixi(2)于是,问题归结为寻找一个满足上述约束条件(1),并使目标函数(2)达到最大的解向量X=(x1,x2,…,xn...&
(本文共5页)
权威出处：
1问题描述给定n种物品和一个背包。物品i的重量是wi,其价值是vi,背包容量是C。问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大。本文主要通过动态规划原理来求解0-1背包问题。2求解问题的动态规划原理将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求...&
(本文共1页)
权威出处：
0-1背包问题[1]是运筹学中多目标优化问题,由决策xi时,问题处于以下两种状态之一:Merkel和Hellman在1978年提出,已被证明是a)背包容量不足以装入物品i,则xi=0背包不增加价值;一个典型的NP-complete问题。从现实应用角度b)背包容量可以装入物品i,则xi=1背包的价值增加了vi。来看,货物的装箱问题、物资的分配和存储问题等都可令V(i,j)表示在前i(1≤i≤n)个物品中能够装入以用0-1背包问题来解决。因此,针对0-1背包问题进行算容量为j(1≤j≤C)的背包中的物品的最大值,则可以得法研究是一件很有必要的工作。到如下的动态规划函数:目前已有的求解方法可分为两大类,一类是精确算V(i,0)=V(0,j)=0(3)法,另一类是近似算法。如动态规划算法、回溯法、分支(4)限界法属于精确算法;如贪婪法、蚁群算法、粒子群算法和遗传算法、二进制差异演化算法、知识进化算法属于近2.3 0-1背包问题的求解过程...&
(本文共2页)
权威出处：
0引言背包问题是一个典型的NP-hard问题,求解背包问题有着广泛的应用前景,在学术上,可以解决0-1整数规划问题或某类可归纳为0-1背包问题的子问题;在实际应用中,对于解决资源分配、投资决策、预算控制、项目选择和货物装运等问题,其规划方法优劣将直接影响到运作效率与成本[1]。因此,对该问题的研究倍受人们关注。文中在对多种不同的求解方法如贪婪算法、回溯法、分枝-界限法等进行分析研究的基础上,采用动态规划算法解决此类问题。通过在Matlab6.5环境下对其算法进行测试,并与其他解决背包问题的方法进行分析对比,表明动态规划方法以空间换时间,对一个问题或多次出现的相同问题仅需解决一次,因此可节省大量的计算时间而具有更高运行效率的优越性。1问题描述背包问题是一个典型的NP难问题,它的数学模型实际上是一个0-1规划问题。0-1背包问题是指有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品且对每一物品,要么选,要么不选,满足被选...&
(本文共3页)
权威出处：
算法设计与分析是一门集应用性、创造性及实践性为一体的综合性极强的课程[1-2]。利用算法求解问题,首先要把实际问题抽象成数学模型,再进行相应的算法设计。这些步骤是一个有机的整体,算法设计是其中的核心内容,是从提出问题到解决问题的关键步骤。在教学过程中,应当采用恰当的方法,才能使学生掌握算法的基本理论和技术。其中,算法设计的规范性是影响学生理解和消化算法思想的重要因素。0-1背包问题(0-1 knapsack problem)是算法分析与设计中一个非常经典的NP完全问题。它的问题描述简单,却是一个相当难解的问题。穷举法[3]可以很容易地在指数时间θ(2n)内解决0-1背包问题,具体方法为:枚举物品集合的所有子集,并选择那个具有最高效用且不超过背包负重c的子集,穷举法是一个效率低下算法。目前比穷举法快速的方法有动态规划、回溯法、分支限界法等[4-5]。其中,回溯法和分支限界法仍然是指数时间算法,只不过通过剪枝函数加速了搜索过程。本文...&
(本文共5页)
权威出处：
时变背包问题(Time-varying Knapsack Problem,TVKP)[1,2]是一种动态0-1背包问题,也是一种动态组合最优化问题,在投资决策、资源分配、装箱问题以及下料问题等研究中具有重要的理论与应用价值。在TVKP问题中,物品的价值、重量和背包载重都是可以动态变化的,从而大大增加了问题的求解难度。由于0-1背包问题(0-1KP)是NP-hard问题,不存在多项式时间算法,而TVKP本质上是多个不同0-1KP的动态组合,因此也是NP-hard问题,不存在多项式时间算法。目前,有关TVKP的研究主要集中于背包载重在两个固定值之间振荡变化的情况,并且它是基于进化算法进行求解的[3-6]。随机时变背包问题(Random Time-varyingKnapsack Problems,RTVKP)[3-6]是TVKP的更一般形式,其物品的价值、重量和背包载重均是随着时间随机动态变化的,这也是难度最大的TVKP问题。本文基于...&
(本文共5页)
权威出处：
扩展阅读：
CNKI手机学问
有学问，才够权威！
出版：《中国学术期刊（光盘版）》电子杂志社有限公司
地址：北京清华大学 84-48信箱 知识超市公司
互联网出版许可证 新出网证(京)字008号
京ICP证040431号
服务咨询：400-810--9993
订购咨询：400-819-9993
传真：010-ustcxcl 的BLOG
用户名：ustcxcl
文章数：22
访问量：1724
注册日期：
阅读量：5863
阅读量：12276
阅读量：306159
阅读量：1023557
51CTO推荐博文
可以这样理解：背包的背负有上限，因此在这个上限内尽可能多的装东西，并且价值越多越好。在这里我之想讨论动态规划解决这个问题的详细过程。动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。因为背包的最终最大容量未知，所以，我们得从1到M一个一个的试，比如，刚开始任选N件物品中的一个，看对应的M的背包，能不能放进去，如果能放进去，并且还有多少空间，则，多出来的空间能放N-1物品中的最大价值，怎么能保证总选则是最大价值呢，看下表：测试数据：10,33,44,55,6650) this.width=650;" style="list-style-type:margin:0padding:0" title="动态规划之０１背包问题" alt="动态规划之０１背包问题" src="/upfile/.jpg" />c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.从以上最大价值的构造过程中可以看出。f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.下面是一种实现过程：（C语言描述）#include&stdio.h&intc[10][100];intknapsack(intm,intn){inti,j,w[10],p[10];for(i=1;i&n+1;i++)scanf("\n%d,%d",&w[i],&p[i]);for(i=0;i&10;i++)for(j=0;j&100;j++)c[i][j]=0;for(i=1;i&n+1;i++)for(j=1;j&m+1;j++){if(w[i]&=j){if(p[i]+c[i-1][j-w[i]]&c[i-1][j])c[i][j]=p[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}elsec[i][j]=c[i-1][j];}return(c[n][m]);}intmain(){intm,n;inti,j;printf("inputthemaxcapacityandthenumberofthegoods:\n");scanf("%d,%d",&m,&n);printf("Inputeachone(weightandvalue):\n");printf("%d",knapsack(m,n));printf("\n");for(i=0;i&10;i++)for(j=0;j&15;j++){printf("%d",c[i][j]);if(j==14)printf("\n");}system("pause");}本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：┆阅读(0)┆评论(0)PHP动态规划解决0-1背包问题实例分析_模板无忧
PHP动态规划解决0-1背包问题实例分析_PHP教程
推荐：这篇文章主要介绍了php找出指定范围内回文数且平方根也是回文数的方法,实例分析了php判断回文的技巧,具有一定参考借鉴价值,需要的朋友可以参考下 本文实例讲述了php找出指定范围内回文数且平方根也是回文数的方法。分享给大家供大家参考。具体如下： 一、要求： 给出两&这篇文章主要介绍了动态规划解决0-1背包问题,实例分析了背包问题的原理与实现技巧,需要的朋友可以参考下
本文实例分析了PHP动态规划解决0-1背包问题。分享给大家供大家参考。具体分析如下：
背包问题描述：一个承受最大重量为W的背包，现在有n个物品，每个物品重量为t,
每个物品的价值为v。
要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大。
思路：定义一个二维数组，一维为物品数量(表示每个物品),二维是重量（不超过最大,这里是15）,下面数组a,
动态规划原理思想，max(opt(i-1,w),wi+opt(i-1,w-wi))
当中最大值，
opt(i-1,w-wi)指上一个最优解
希望本文所述对大家的程序设计有所帮助。分享：这篇文章主要介绍了PHP判断一个字符串是否是回文字符串的方法,实例分析了php操作字符串判断回文的技巧,具有一定参考借鉴价值,需要的朋友可以参考下 本文实例讲述了PHP判断一个字符串是否是回文字符串的方法。分享给大家供大家参考。具体实现方法如下： ? 希望本文所述
&&&&&&&&&&&&
相关PHP教程：
编程教程搜索
PHP教程推荐
猜你也喜欢看这些