点击上方“Jerry的算法和NLP”，选择“星标”公众号

   背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题.

   有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 

第一行两个整数，N,M空格隔开，分别表示物品数量和背包容积。

接下来有N行,每行两个整数vi,wi,空格隔开,分别表示第i件物品的体积和价格

输出一个整数，表示最大价值。

0/1背包问题是最基本的背包问题，每个物品最多只能放一次或者选择不放。

   思路A：一共有n个东西，背包容量为m，对于每个物品我们有两种选择方案，一个物品有两种，两个物品有四种，三个物品有八种，那么n个物品就有2^n种方案。穷举这2^n种方案，当n=100的时候，等于多少？

   这个数值是非常大的，例如存在一张可以充分折叠的纸厚度为0.1毫米，对半折一次，则厚度是0.2mm，再对折一次，是0.4mm……由此类推，对折n次，那么纸的厚度是：(2^n)×0.1mm

    这个厚度的增长将呈指数增长的趋势，那么折了100次后，那么其长度到“134亿光年”，而宇宙大爆炸至今的全部时间仅仅才137亿年。

   思路B：动态规划的思想本质就是找到递归的表达式。在找递归的表达式的时候肯定是存在一定的边界限制（如青蛙跳台阶这种题目就没有限制）

   那么这道题它给出了一个边界限制：容量M，当容量满的时候就再也放不下东西了，故我们在进行递归的时候需要考虑当前的容量，这就是我们的限制条件

这个递归函数要怎么写？

    这道题我打算用一维数组的做法来做，我先初始化一个数组叫f，长度为m+1(为了索引从1-m代表着容量从1-m),最后取f的最后一个元素即为答案。那么这个递归函数就可以表示为

f(m)  当前背包容量为m的情况下不选择当前物品

 m-w[i]代表着我这个背包在上一次选择中必须至少给我留下w[i]的空间，我才可以选择当前物品，然后得到它的价值v[i]

   其次开始遍历我的物品，一共n个，遍历我每一个物品的时候我都会使得我的背包容量依次递增（从1到m）。这一步什么意思？我们来举个例子

...???  好像走错片场了。我们这个问题的前提是每个物品只能选择一次或者不选择使得利益最大化，那如果这个背包容量容量从1开始一直递增，我们这个问题就变成了每个物品可以选择多次。

    为什么会变成这种情况，因为背包容量如果从少到多，它每次贪心max()的时候都会想，我还能不能放入更多的这个物品，现在放入一件了，能不能再放多一件。

     这种情况，因为背包容量如果从多到少，它每次贪心max()的时候，都是先看能不能放下一件当前物品,不会产生放置两件物品以上的情况。

注意：分歧其实就在f[m-w[i]]，

如果容量从小到大遍历，那么到最后的f[m]取决的结果不是基于上一物品选择,而是取决于当前物品的选择

如果容量从大到小遍历，那么到最后的f[m]取决的结果是基于上一物品选择

 1# 01背包问题 利用一维数组进行
10# 定义一个数组 f[j] 表示容量为j的情况下能放的总价值最大
20# j为容量不断上升 当容量大于当前的时候才可以放下这个

• 022-从上往下打印二叉树

• 023-二叉搜索树的后序遍历序列

• 024-二叉树中和为某一值的路径

• 026-二叉搜索树与双向链表

• 059-按之字形顺序打印二叉树

• 060-把二叉树打印成多行

• 062-二叉搜索树的第k个结点

• 005-用两个栈实现队列

• 021-栈的压入、弹出序列

• 044-翻转单词顺序列(栈)

• 064-滑动窗口的最大值(双端队列)

• 034-第一个只出现一次的字符

• 006-旋转数组的最小数字（二分查找）

• 037-数字在排序数组中出现的次数（二分查找）

• 030-连续子数组的最大和

• 052-正则表达式匹配(我用的暴力)

• 035-数组中的逆序对(归并排序)

• 029-最小的K个数(堆排序)

• 029-最小的K个数(快速排序)

• 011-二进制中1的个数

• 012-数值的整数次方

• 013-调整数组顺序使奇数位于偶数前面

• 028-数组中出现次数超过一半的数字

• 031-整数中1出现的次数（从1到n整数中1出现的次数）

• 032-把数组排成最小的数

• 041-和为S的连续正数序列(滑动窗口思想)

• 042-和为S的两个数字(双指针思想)

• 043-左旋转字符串(矩阵翻转)

• 046-孩子们的游戏-圆圈中最后剩下的数(约瑟夫环)

剑指offer刷题交流群

  扫码添加微信，一定要备注研究方向+地点+学校+昵称（如机器学习+上海+上交+汤姆），只有备注正确才可以加群噢。