r**h
发帖数: 1288 | 1 子集和问题：给定一个整数集合S和整数N，问是否存在S的一个子集满足所有元素的和
为N。
根据背包9讲上的说法这个问题是NPC问题，和0-1背包问题不相同必须要搜索解。可是
我一直都看不出来区别在哪里。。。为什么子集和问题不能转换成0-1背包问题，然后
在O(|S|N)的时间复杂度之内解决呢？ |
s*******a
发帖数: 8827 | 2 isn't bean packing also np hard?
【在 r**h 的大作中提到】
: 子集和问题：给定一个整数集合S和整数N，问是否存在S的一个子集满足所有元素的和
: 为N。
: 根据背包9讲上的说法这个问题是NPC问题，和0-1背包问题不相同必须要搜索解。可是
: 我一直都看不出来区别在哪里。。。为什么子集和问题不能转换成0-1背包问题，然后
: 在O(|S|N)的时间复杂度之内解决呢？
|
r**h
发帖数: 1288 | 3 但是背包问题可以用DP优化到O(MN)啊
不是很理解为什么子集和问题一定要用搜索
【在 s*******a 的大作中提到】
: isn't bean packing also np hard?
|
g****y
发帖数: 2810 | 4 我感觉这个意思是不用考虑N的大小的，如果N非常大，或者N不是整数，就不是0－1背
包问题能解决的了,如果S中的数字个数不多，那么搜索的时间应该远小于N的.
【在 r**h 的大作中提到】
: 但是背包问题可以用DP优化到O(MN)啊
: 不是很理解为什么子集和问题一定要用搜索
|
