现在的位置: 首页 > 综合 > 正文

01背包状态方程详解

2018年04月25日 ⁄ 综合 ⁄ 共 438字 ⁄ 字号 评论关闭

之前看过一段时间的背包,算不上学,纯属是背模板,因此,摔了一大跟头,自此发奋,今重看背包,以下是自己目前的理解。

有兴趣可以看看背包状态方程解析,讲的非常精彩。

我是根据模板加以理解的,因此,首先给出状态方程模板如下:

for(int i = 1; i <= N; i++)
{
        for(int j = V; j <= Vdata[i]; j--;)
        {
                 dp[j]=max(dp[j],dp[j-Vdata[i]]+D[i]);
         }
}

其中,N表示物品数,V代表背包的重量或者是体积,Vdata存储的是每件物品所占的重量或体积,D存储的是每件物品的价值。

最外层的for循环用于枚举每件物品,第二层for循环用于得到当背包容量或体积为J时,背包最大的价值量。dp[j]代表体积为j的时候的最大价值量,dp[j-Vdata[i]]+D[i]代表加入第i件产品时的最大价值量。

整个二重循环可以理解为:加入第i件产品后,不同的容量下的最大价值量。

简单的一个状态方程,想了一天才弄明白~~~~~~加油!

欢迎大家提出不同意见~谢谢~

抱歉!评论已关闭.