01背包

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。

01背包题目的雏形是：

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

从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或不放。

其状态转移方程是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

对于这个方程其实并不难理解，方程之中，现在需要放置的是第i件物品，这件物品的体积是c[i],价值是w[i],因此f[i-1][v]代表的就是不将这件物品放入背包，而f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。

以上来自度娘。传送门:https://baike.baidu.com

自己看了好几篇博客，然后感觉，说这么多不如直接手写个表来的实际，

传送门:http://blog.csdn.net/mu399/article/details/7722810

把这篇博客看完，那个表自己手写填上差不多就理解了，然后就是填上表之后和代码联系在一起怎么想啊，可能我太菜了，开始怎么都不理解，我的智商可能离家出走了，后来知道了。

对于背包问题，通常的处理方法是搜索。用递归来完成搜索。

用f[i,j]表示在前 i 件物品中选择若干件放在已用空间为 j 的背包里所能获得的最大价值，

所以关键代码就是:

f[i, j] = max( f[ i-1 ][  j-W[ i ] ] + P[ i ] , f[ i-1 ][ j ] )//j >= W[ i ]

再来个博客就可以了，传送门:http://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

这么多大佬写的这么好，看他们写的真的很厉害啊?????

我这么菜(?﹏?)

打击!!＿|￣|○

加油。

动态规划-01背包

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们