C**********n
发帖数: 100 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: CplusplusFan (C++ Fan), 信区: JobHunting
标 题: 请教背包问题。
发信站: BBS 未名空间站 (Fri Oct 30 16:07:55 2009, 美东)
不是说背包问题是经典的NP问题吗，
可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。 |
s******g
发帖数: 3841 | 2 1.你先把NP问题的定义搞搞清楚，以及NPC,NP-hard的区别
2.就算是NP hard也得有个解法啊，不能因为是NP-hard就不解了。老师要你分解质因数
，你能说分解质因数是NPhard就不做题了吗？ |
l******e
发帖数: 470 | 3 背包有伪多项式时间算法，说它是“伪”
就是因为复杂度是背包大小（比如说N)的多项式
而实际上一般说多项式是相对input size来说的，在这里表示N只要logN个bit，从这个
意义上是NPC
【在 C**********n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: CplusplusFan (C++ Fan), 信区: JobHunting
: 标 题: 请教背包问题。
: 发信站: BBS 未名空间站 (Fri Oct 30 16:07:55 2009, 美东)
: 不是说背包问题是经典的NP问题吗，
: 可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。
|
s******g
发帖数: 3841 | 4 还有伪多项式这一说法。。。。
那分解质因数也是伪多项式了，枚举的话也只要N，如果N是数字大小的话，哈哈
【在 l******e 的大作中提到】
: 背包有伪多项式时间算法，说它是“伪”
: 就是因为复杂度是背包大小（比如说N)的多项式
: 而实际上一般说多项式是相对input size来说的，在这里表示N只要logN个bit，从这个
: 意义上是NPC
|
S*******w
发帖数: 24236 | 5 这不是太常见了吗
学cs的一般都会学到
【在 s******g 的大作中提到】
: 还有伪多项式这一说法。。。。
: 那分解质因数也是伪多项式了，枚举的话也只要N，如果N是数字大小的话，哈哈
|
C*********h
发帖数: 74 | 6 少见多怪。
因为这个多项式不是input size的多项式：
背包大小是N,但是input size是log(N).
【在 s******g 的大作中提到】
: 还有伪多项式这一说法。。。。
: 那分解质因数也是伪多项式了，枚举的话也只要N，如果N是数字大小的话，哈哈
|
s******g
发帖数: 3841 | 7 你看懂了我的话没有
【在 C*********h 的大作中提到】
: 少见多怪。
: 因为这个多项式不是input size的多项式：
: 背包大小是N,但是input size是log(N).
|
T*****9
发帖数: 2484 | 8 动态规划很多时候时间复杂度都不是指数
【在 C**********n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: CplusplusFan (C++ Fan), 信区: JobHunting
: 标 题: 请教背包问题。
: 发信站: BBS 未名空间站 (Fri Oct 30 16:07:55 2009, 美东)
: 不是说背包问题是经典的NP问题吗，
: 可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。
|
v********e
发帖数: 1058 | 9 factoring本来就是有伪多项式算法啊，有什么好笑的？
你前面的帖子说factoring是NP hard，你要给个证明也能出一把名了。
【在 s******g 的大作中提到】
: 还有伪多项式这一说法。。。。
: 那分解质因数也是伪多项式了，枚举的话也只要N，如果N是数字大小的话，哈哈
|
c******t
发帖数: 1500 | 10 floating Knapsack可以用greedy来解
0-1 Knapsack是NP-complete的 |
|
|
s******g
发帖数: 3841 | 11 NPhard是我说错了
但是我从来没有听说过有伪多项式这一说法，P就是P，NPC就是NPC。把一个NPC/NPhard
分类为伪多项式有什么意义呢？
【在 v********e 的大作中提到】
: factoring本来就是有伪多项式算法啊，有什么好笑的？
: 你前面的帖子说factoring是NP hard，你要给个证明也能出一把名了。
|
p***o
发帖数: 1252 | 12 NP Hard为什么不能继续细分？
http://en.wikipedia.org/wiki/PSPACE
NPhard
【在 s******g 的大作中提到】
: NPhard是我说错了
: 但是我从来没有听说过有伪多项式这一说法，P就是P，NPC就是NPC。把一个NPC/NPhard
: 分类为伪多项式有什么意义呢？
|
a**n
发帖数: 132 | 13 你没听说过不等于不存在或是没意义
就好比很多问题已经是P了，还reduce time complexity干什么？
还研究strongly polynomial干什么
NPhard
【在 s******g 的大作中提到】
: NPhard是我说错了
: 但是我从来没有听说过有伪多项式这一说法，P就是P，NPC就是NPC。把一个NPC/NPhard
: 分类为伪多项式有什么意义呢？
|
l******e
发帖数: 470 | 14 意义在于这个问题还能“伪”一把，很多问题伪都伪不了。。
而且一大类类似的可以动态规划的的“伪多项式”可以转化成有任意精度的“真多项式
”近似算法。
NPhard
【在 s******g 的大作中提到】
: NPhard是我说错了
: 但是我从来没有听说过有伪多项式这一说法，P就是P，NPC就是NPC。把一个NPC/NPhard
: 分类为伪多项式有什么意义呢？
|
r****o
发帖数: 1950 | 15 多谢，请问哪些算法是真正的多项式时间而非伪多项式时间呢？
比如说某个算法复杂度为O(NG)，那G可以很大，大到2^N不就是指数的呢吗？那岂不所
有类似的算法都是伪多项式?
【在 l******e 的大作中提到】
: 背包有伪多项式时间算法，说它是“伪”
: 就是因为复杂度是背包大小（比如说N)的多项式
: 而实际上一般说多项式是相对input size来说的，在这里表示N只要logN个bit，从这个
: 意义上是NPC
|
f**f
发帖数: 171 | 16 动态规划是一种思路，不是说某个问题有动态规划算法就表示该问题是多项式复杂度
很多strongly NP hard问题，有O(2^n)的动态规划算法
【在 r****o 的大作中提到】
: 多谢，请问哪些算法是真正的多项式时间而非伪多项式时间呢？
: 比如说某个算法复杂度为O(NG)，那G可以很大，大到2^N不就是指数的呢吗？那岂不所
: 有类似的算法都是伪多项式?
|
T*****9
发帖数: 2484 | 17 有道理
不所
【在 f**f 的大作中提到】
: 动态规划是一种思路，不是说某个问题有动态规划算法就表示该问题是多项式复杂度
: 很多strongly NP hard问题，有O(2^n)的动态规划算法
|
r****o
发帖数: 1950 | 18 谢谢。
但是这里01背包问题的时间复杂度是O(NG)，不是指数。
【在 f**f 的大作中提到】
: 动态规划是一种思路，不是说某个问题有动态规划算法就表示该问题是多项式复杂度
: 很多strongly NP hard问题，有O(2^n)的动态规划算法
|
v********e
发帖数: 1058 | 19 G是什么东西啊？如果是输入的一部分，N是输入的另一部分，G大到2^N的话那O(NG)基
本就是个O(G)时间的算法，线性的，很快了。如果G不是输入的一部分，那要限制G，否
则写成O(NG)没什么意思
算法的时间复杂度就是运行时间和输入长度的一个比较，你好像基本概念不太清楚。
【在 r****o 的大作中提到】
: 多谢，请问哪些算法是真正的多项式时间而非伪多项式时间呢？
: 比如说某个算法复杂度为O(NG)，那G可以很大，大到2^N不就是指数的呢吗？那岂不所
: 有类似的算法都是伪多项式?
|
v********e
发帖数: 1058 | 20 这里N是什么啊？是背包的capacity吗？如果是的话，N在输入中的长度是log N，在运
行时间里占了N，两相比较不就是指数级么
【在 r****o 的大作中提到】
: 谢谢。
: 但是这里01背包问题的时间复杂度是O(NG)，不是指数。
|
|
|
l******e
发帖数: 470 | 21 比如说检查一个数N是不是prime number
就可以有poly(logN)的算法，这个就是输入大小的多项式
【在 r****o 的大作中提到】
: 多谢，请问哪些算法是真正的多项式时间而非伪多项式时间呢？
: 比如说某个算法复杂度为O(NG)，那G可以很大，大到2^N不就是指数的呢吗？那岂不所
: 有类似的算法都是伪多项式?
|
C*********h
发帖数: 74 | 22 en,primes is in P 那篇paper还是很牛的。
有些cs phd学了半天基本的概念都是乱的。
【在 l******e 的大作中提到】
: 比如说检查一个数N是不是prime number
: 就可以有poly(logN)的算法，这个就是输入大小的多项式
|
l******e
发帖数: 470 | 23 乱是因为很多计算模型，一般大家说某具体问题时间复杂度啊什么的都不明确说是在那
个模型下，一般就认为是对这个具体问题最make sense的模型。
比如排序nlogn，实际上假设了比较可以O(1)做完。
背包里背包的大小N这个数值matter，要是做min spanning tree，一般来讲每条边具体
长度的数值不matter，加减乘除都假设O(1),但要换个模型，复杂度就不一样了。。。
乱的我一般也搞的不太清楚
【在 C*********h 的大作中提到】
: en,primes is in P 那篇paper还是很牛的。
: 有些cs phd学了半天基本的概念都是乱的。
|
