动态规划-01背包

时间：2017-07-22 22:02:53 阅读：288 评论：0 收藏：0 [点我收藏+]

先认错，学长们很早之前就讲过了，然而我现在才来写。。。

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

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

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

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

用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/ZERO-/p/7222876.html

踩

(0)

评论一句话评论（0）

分享档案

更多>