数学 背包问题本页总览背包问题阐述 背包问题是指在给定的重量限制下，在背包中拿取最多的物品。根据限制的不同，背包问题有很多的变种： 0-1 背包问题 maximize ∑i∈Ivixi, subject to ∑i∈Iwixi≤K\text{maximize }\sum_{i\in I}v_ix_i,\text{ subject to }\sum_{i\in I}w_ix_i\le K maximize i∈I∑vixi, subject to i∈I∑wixi≤K 其中 xi∈{0,1}x_i\in\{0,1\}xi∈{0,1}. 这个问题存在一个经典的动态规划解法。 实例 性质 相关内容 参考文献