本文主要是介绍【白话算法】从0-1背包到无限制背包，到背包变种。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先上题目：
0-1背包： 给定n个物品，考虑他们的重量 和 价值，分别为 w[0], w[1], w[2], w[3] ... w[n-1] 和 v[0], v[1], v[2], v[3], v[4] ... v[n-1]。 现在有一个载重量为 W 的背包，求这个背包能放入的物品组合的最大价值。（每个物品只有一件）。
物品数量无限制背包： 给定n种物品，考虑各个种类的物品单件的 重量 和 价值，分别为 w[0], w[1], w[2], w[3] ... w[n-1] 和 v[0], v[1], v[2], v[3], v[4] ... v[n-1]。 现在有一个载重量为 W 的背包，求这个背包能放入的物品组合的最大价值。（每种物品数量无限，可以任意取）。
考虑 0-1 背包问题， 先来把最容易想到的动态规划算法写出来。
我们设d[i][j] 表示 前 i 个物品在背包容量为j下的最优价值。
这时候，
对于第 i个物品 （物品下标从 0开始），
d[i+1][j] 表示 前i+1个物品(即第0号、第1号、……第i号) 在背包容量为j 下的最优价值。
【NOTE】 前i+1个物品分别为 第0号、1号、……i个物品。在动态规划算法实现过程中，正确使用数组下标，可以节省很多控制代码。本算法中，大致规则为：如果使用正向推演（从第一个开始往后），那么需要把第0行数据初始化为0，即第0行代表前0个对象，价值显然为0；第一行代表前一个物品（即第0号物品）。如果使用逆向推演（从最后一个开始往前），那么需要把最后一行（第n行）数据初始化为0，即第0行代后（n-0=n）个物品，第n行代表后（n-n=0）个物品ÿ
这篇关于【白话算法】从0-1背包到无限制背包，到背包变种。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
