背包算法可以用来判断如何使收益最大化，那么什么是背包算法呢？

让我们从一个经典的案例说起

假设现在有一个背包，容量是50，还有一堆物品（如图），各自有自己的重量和价值，要求在【不超重】的情况下带走最高的价值

让我们来看看几种方案

💡贪心算法（不足）【图一】
如果第一次接触背包问题，可能会考虑贪心算法，即每次都考虑带走【最轻】的，这样能带走最多的物品

当然，这是一种理想化的方案，因为物品的重量未必和价值就成正比

我们看图一中，虽然选择了最轻的10和20，价值160，但实际上【最优解】是20和30，价值220

💡动态规划（未优化）【图二】

执行后可以发现，动态规划得出了我们想要的结果，但是目前还有问题：

✨在这段代码中，动态规划状态的转移只与上一行的结果有关，因此可以使用一维数组来记录状态，减少内存消耗并提高计算速度

✨在当前轮次中，当物品重量小于等于当前容量时，可以选择放入或不放入该物品，只需比较两种情况下的最大价值即可，无需再次取两个状态的最大值

✨如果对物品按照单位重量价值进行排序，可以先选取单位重量价值高的物品，从而使得每次选择的物品更有可能达到最优解，减少计算次数

💡动态规划（优化）【图三】
根据上面总结的三条，我们可以得出优化方案（图三）

[玫瑰]那么本文就到此结束了，下一期考虑开个新系列，和密码学相关，感兴趣可以期待一下

[彩虹]pluie
[彩虹]2023-09-22

微信扫码关注公众号 更新内容早知道