背包问题是NPC的，动态规划解法不是o(nC)么- 饮水思源

【 在LSD 的大作中提到: 】 : 背包问题的输入input = logC（C的二进制字长），这样DP复杂度对应于输入是theta.. : 2^input）。所以是np的。所以称背包问题的DP解法是伪 ...

bbs.sjtu.edu.cn