20211225-如何理解0-1背包是NPC问题

发表于 2021-12-25 阅读次数：本文字数： 315 阅读时长 ≈ 1 分钟

如何理解0-1背包是NPC问题?

1. 分析

在0-1背包问题中，我们需要2个输入（一个数组和一个整数）来解决这个问题。

n个项目的数组$\{n_1, n_2, …\}$，每个项目都有它的价值指数和权重指数；

整数W作为最大可接受的重量。

假设n=10, W=8，则：

n = [n1, n2, ..., n10], W=1000，因此时间复杂度为T（n）= O（nW）= O（80）。

若将n的大小加倍：T（n）= O（nW）= O（20 * 8）= O（160）;

若将W的大小加倍：并不意味着W = 20，而是长度是两倍，即W = 10000000，因此：T（n）= O（nW）= 0（10 * 128）= 0（1280）；

因此所需时间以指数增加，这是一个NPC问题。

因此，它是一个伪多项式。