一文读懂背包问题（附经典例题详解）

背包问题，一直以来雄踞Google、Facebook等一线大公司面试题型必考榜首，同时，也是一不留神就会跪的面试题。 一听背包问题就发怵？其实，背包问题也没那么难。 1.什么是背包问题？背包问题 (Knapsack problem) 是一种组合优化的NP完全问题。 一般来说，就是给定一组有固定价值和固定重量的物品，以及一个已知最大承重量的背包，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。如果用一句话形象地描述，大概就是：有个小偷半夜闯入豪宅，可以偷的东西非常多，但是负重能力有限，偷哪些东西才更加不枉此行？（误） 这一类问题是典型的使用动态规划解决的问题，我们可以把背包问题分成3种不同的子问题：0-1背包问题、完全背包和多重 ………………………………