第三周DP1.1

动态规划(一)

背包问题分类

01背包问题

N个物品,容量为V的背包,每个物品两个属性,价值Wi,体积Vi,体积V以内,挑选一些物品,目的是物品的总价值最大,询问最大值是多少。

特点:每件物品只能用一次。

完全背包问题

N个物品,容量为V的背包,每个物品两个属性,价值Wi,体积Vi,体积V以内,挑选一些物品,目的是物品的总价值最大,询问最大值是多少。

特点:每件物品有无限个。

多重背包问题

N个物品,容量为V的背包,每个物品两个属性,价值Wi,体积Vi,体积V以内,挑选一些物品,目的是物品的总价值最大,询问最大值是多少。

特点:每个物品有Si个(Si不相同)。

分组背包问题

物品有N组,每一组物品里有若干个,容量为V的背包,每个物品两个属性,价值Wi,体积Vi,体积V以内,挑选一些物品,目的是物品的总价值最大,询问最大值是多少。

特点:每一组只能选一个。

DP问题考虑角度

状态表示f[i,j]----集合和属性

f[i,j]表示的某种限制条件下的一个集合,f[i,j]的值代表这个集合中的某种属性,历如max,min等……

状态计算-----集合的划分

遵循一般性原则——不重不漏的原则

将集合中所有选法分为两大类,含i和不含i的情况,然后取想要的属性的值出来。

01背包问题笔记

状态表示f[i,j]

f[i,j]代表选取前i件物品,在体积j下所有选法的集合,具体数值代表这些集合中的最优解,属性为价值的最大值。

状态转移方程
f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i] )

将所有选法的集合划分成两类,选第i个和不选第i个两类。但是f[i,j]选取的第i个物品的值没有办法根据前面的状态直接转移出来,所以我们根据不等式两边同时减去一个相等数,等式不变的原则,将选取状态倒退回上一个没选取第i个物品的状态(上个状态最优解),再加上第i个物品的价值,可以得到f[i,j]选取第i个物品的数值,两类取个max,状态转移完成。

状态转移代码以及过程打表
for( int i = 1 ; i <= n ; i++ )//
        for( int j = 0 ; j <= m ; j++ )//
        {
            f[i][j] = f[i-1][j];
            if(  j >= v[i] ) f[i][j] = max( f[i-1][j-v[i]]+w[i],f[i][j]);
            //j-v[i]是不会越界的,取等号的时候只选取i,大于的时候会找前面的已经转移好的状态,若无f[i,j] = 0
        }

image

01背包一维滚动数组优化f[j]

将二维的状态表示转化成为N件物品下,体积j内的最优解。

代码表示以及状态转移打表
 for( int i = 1 ; i <= n ; i++ )//n个物品
        for( int j = m ; j >= v[i] ; j-- )//n物品下体积
        {
            f[j] = max( f[j-v[i]]+w[i],f[j]);
        }

image

一维需要从大体积枚举到小体积的原因就在此,我们每次从后往前更新数组时,都能保证前面的数组是前一个状态的最优解。

而如果从小到大更新,那么在第i个物品的选取的最优解已经出现的情况下,可能还会出现重复选取第i个物品的情况,与题设不符合。

错误转移过程如下(第一行)

image

评论

暂无评论