今天抓的四道DP做完了==三道是用背包做的，突然想起来背包知识点总结还没做~反正时间还早。。把01背包和完全背包小结了吧~~福利来啦~~噶呜~

01背包：

基本思路：

01背包问题是最广为人知的动态规划问题之一，介绍01背包之前，先来看一个引例：

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

这是最基础的背包问题，特点是：每件物品只有一件，选择放或者不放。

由以上的特点，我们可以写出状态转移方程：
          f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 
    这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的 
     如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，
     价值为f[i-1][v]；
     如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，
     此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度：

以上方法的时间空间复杂度为O（VN）;能优化到O(N)；该思路如何实现呢？

主循环肯定是（1~N），如果用一个数组f[0~V]能不能保证第i次结束后f[v]中表示的就是我们定义的状态f[i][v]呢？

f[i][v]是由f[i-1][v],f[i-1][v-c[i]]两个子问题递推而来的，能否在推f[i][v]的时候也能够得到f[i-1][v],f[i-1][v-c[i]]的值呢？事实上，只要我们每次主循环中以v=V~0

的顺序推f[v],就能保证f[v]是f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。

伪码：
  　　for i=1..N 
  　　　　for v=V..0 
   　　 　　f[v]=max{f[v],f[v-c[i]]+w[i]};

为了方便使用，写出01背包的过程：

zreoonepack（cost，weight）//cost和weight分别表示这件物品的费用和价值

for v:V~cost

do f[v]=max(f[v],f[v-cost]+weight).

有了这个过程，01背包的伪码就写成啦：

for i:1~N

do zreoonepack（c[i],w[i]）;

初始化细节问题：

在求最优解背包的问题中，要特别注意题目的问法~：是否要求恰好装满背包！！

如果是要求恰好装满背包，在初始化时除了f[0]=0外，其他f[1~V]均设为负无穷~~

若没有要求，初始化时只需要将f[0~v]全部设为0.

下面简述原因：

如果要求恰好装满背包，那么此时只有容量为0的背包可能被价值为0的nothing恰好装满，其他容量背包均无合法解。

一个常数优化：

for i=1..N 
  　　　　for v=V..0 
   　　 　　do。。。

可以将这个循环的下限进行改进：由于只需要最后f[v]的值，倒推前一个物品，其实只需要知道f[v-w[n]]即可，所以代码可以改成

for i=1..N

do bound:max(V-sumw[i~n],c[i])
  　　　　for v=V..to bound
   　　 　　do。。。

这么详细的讲解，小盆友们都会了吧？~噶呜~~

随机推荐

1. 关于pl/sql数据库下拉中选项为空的问题

   1.可能是在配置环境变量TNS_ADMIN的时候后面多了一个分号,去掉分号就可以了

2. 现在web前端这么火，钱景怎么样啊？

   web前端开发工程师可以说是一个全新的职业,在IT整个行业中真正受到重视的时间没有超过5年,也正因为这样,大家越来越想了解web前端工程师的前景究竟怎么样? web前端培训就业前景如何?web前端工程 ...

3. SSH+Ext+mysql快速开发

   一.需要知识点 1.SSH整合 2.EXT使用 以及深入细节点 二.小功能实现 1.Servlet实现校验码验证 2.首页布局实现 3.struts错误信息显示(struts标签使用) 4.首页整体布 ...

4. 文件夹差异文件对比工具 meld

   /***************************************************************************************** * 文件夹差异文件 ...

5. 获得随机的n条结果行

   * FROM [Menu] order by NEWID() * FROM [Menu]

6. C#简单邮件发送

   System.Net.Mail.MailMessage message = new System.Net.Mail.MailMessage(); message.From = new System.N ...

7. C++智能指针 auto_ptr、shared_ptr、weak_ptr和unique_ptr

   手写代码是理解C++的最好办法,以几个例子说明C++四个智能指针的用法,转载请注明出处. 一.auto_ptr auto_ptr这是C++98标准下的智能指针,现在常常已经被C++标准的其他智能指针取 ...

8. 真实世界的脉络].（英）戴维．多伊奇.pdf

   [真实世界的脉络].(英)戴维．多伊奇.pdf 宇宙.时间.生命.等等,如果用量子物理学.计算机科学.进化论.认识论将这些最基本而又复杂的问题纠缠在一起时,那将会是一幅什么样的图景呢?也许,我们穷尽一 ...

9. 在windows中把一个文件夹打成war包

   转: 在windows中把一个文件夹打成war包 一般开发打war包时都是用MyEclipse或IntelliJ IDEA等直接导出war文件,这里介绍一种如何把一个文件夹打成war包的方式,如下   ...

10. mysql5.7 rpm安装教程

    注意版本和此次更新时间 2017-12-03  版本:mysql-5.7.20-1.el6.x86_64  环境:linux6.x ​官方下载地址: wget https://dev.mysql.co ...