面试官：你完全不懂背包问题，难道自己能解决，还是需要我指导？

本文共计3134个文字，预计阅读时间需要13分钟。

从零开始，深入剖析背包问题，分析动态规划路径。从设计动态转移方程，到优化空间复杂度，带你全面提升！面试官：背包问题并非全部都会，是你自己走，还是我带你？在面试中，关键在于自我探索。

带你从0开始深入剖析完全背包问题，分析动态规划问题的套路，从0设计动态转移方程，带你优化数组空间！！！ 面试官：完全背包都不会，是你自己走还是我送你？

在如今的面试当中算法题已经成为面试不可或缺的内容，今天就跟大家分享一个还比较困难的笔试题——完全背包。

完全背包问题

有\(N\)种物品和一个容量是 \(V\)的背包，每种物品都有无限件可用。第\(i\) 种物品的体积是 \(v_i\)，价值是\(w_i\)。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

完全背包问题和01背包的唯一区别就在于物品的个数，在01背包当中所有的物品只有一件，也就只能使用一次。而在完全背包当中物品可以使用无限多次。

比如下面的4个物品，背包能够承受的最大重量为5，我们应该如何选择，使得我们获得的总价值最大：

物品 重量 价值 A 1 2 B 2 4 C 3 4 D 4 5

这个问题还是比较简单，我们直接从图中看，我们可以选择五个A或者两个B一个A，可以产生最大的收益，最大收益为10。