本文主要是介绍背包九讲笔记-完全背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
基本思路
完全背包就是01背包的变化，所有的物件不再是单一的，而有无限个，可以先用01背包的思路，让所有的每种物品都装尽量多，那么我们可以获得状态转移方程：
F[i,v] = max{F[i − 1,v]，F[i − 1,v − kCi] + kWi| 0 ≤ kCi≤ v}
或者是：
F[i,v] = max{F[v]，F[v − kCi] + kWi| 0 ≤ kCi≤ v}
（优化同01背包）
？疑问：？
2.4 转化为 01 背包问题求解
01 背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为 01 背包问
题来解。
最简单的想法是，考虑到第 i 种物品最多选 ⌊V /Ci⌋ 件，于是可以把第 i 种物品转
化为 ⌊V /Ci⌋ 件费用及价值均不变的物品，然后求解这个 01 背包问题。这样的做法完
全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为 01 背包问题的思
路：将一种物品拆成多件只能选 0 件或 1 件的 01 背包中的物品。
更高效的转化方法是：把第 i 种物品拆成费用为 Ci2k、价值为 Wi2k的若干件物
品，其中 k 取遍满足 Ci2k≤ V 的非负整数。
这是二进制的思想。因为，不管最优策略选几件第 i 种物品，其件数写成二进制后，
总可以表示成若干个 2k件物品的和。这样一来就把每种物品拆成 O(log⌊V /Ci⌋) 件物
品，是一个很大的改进。
O(V N) 的算法
在01背包中，可以把二维数组变为一维数组，但是要注意循环的顺序变换，但是在，完全背包中，把二维变为一维却不需要变化，因为01背包中每种物品只能选一次，而完全背包却不必在意，完全背包的物品好多。
这篇关于背包九讲笔记-完全背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
