背包问题 | MSTBL的博客

https://mstbl.github.io/algorithm/knapsack/ 

 背包问题背包问题有许多种，其中最简单的形如最优装载问题:给出n个物体，第i个物体的重量为wi。在总重量不超过c的前提下选择尽可能多的物体。这种问题就是最简单的贪心问题，用贪心算法就能得到最优解。 复杂一些的是部分背包问题。这类题在最优装载问题的基础上给了每个物体价值vi。也可以用贪心算法做，根据每个物体的性价比贪心就行。 0-1背包问题而对于更复杂的0-1背包问题，背包问题就不一定能得到最优解了。