第三周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
}
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]);
}
一维需要从大体积枚举到小体积的原因就在此,我们每次从后往前更新数组时,都能保证前面的数组是前一个状态的最优解。
而如果从小到大更新,那么在第i个物品的选取的最优解已经出现的情况下,可能还会出现重复选取第i个物品的情况,与题设不符合。
错误转移过程如下(第一行)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论