动态规划
状态表示
集合:选法集合
属性:最优选择
状态计算
集合的划分
一、背包问题
01背包问题
#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--){
//f[i][j]=f[i-1][j];仅仅是个赋值语句 在v[i]>j时保持更新。
//显然,f[j]=f[j]中右侧的f[j]是i-1中的f[j]。
f[j]=max(f[j],f[j-v[i]]+w[i]);
// if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);这里f[i-1][j]也可以写成f[i][j]。
// 若从大到小遍历j,那么对于k<j,f[k]都是第i-1次遍历时的状态,max(f[j],f[j-v[i]]+w[i])等价。
}
cout<<f[m]<<endl;
return 0;
}
状态表示
集合:所有只考虑第i个物品前的且总体积不大于j的所有选法。
属性:在所有集和中,价值最大的选法。
状态计算
集合的划分:总是在(第 i - 1个)状态最优时,计算第 i 个状态。
背包已经最优,故对于任意容积、前 i - 1个物品,背包总是足够满的。
当前状态 f [ i ] [ j ] 总是 f [ i - 1 ] [ j ] 和 f [ i - 1 ] [ j - v [ i ] ] 更新而来。
-
f[i][j]=f[i-1][j];
,不管容积 j 够不够,第 i 个物品还没装进去,故价值直接赋值 i - 1 的最优状态下的价值。 -
if(j<v[i])
,v [ i ] 比每一个 j 都大,装不进去。 -
if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
比较两种状态的价值,找出最优状态。
两种状态
(1)第 i 个物品被选择:
-
f[i][j]=f[i-1][j-v[i]]+w[i];
由上一个最优状态( i - 1个物品,容积为 j - v [ i ]时的最大价值)更新而来。背包有空间,剩余容积足够,直接装入,价值更新。 - 可以理解为一个原来价值最大的满背包,外接了第 i 个物品(白嫖的价值肯定最优)。
(2)第 i 个物品未被选择:
-
f[i][j]=f[i-1][j];
,背包有空间,但剩余容积不够,装不进去,价值不变。 - 对于每个物品 i,总可以找到一个对应的容积 j,将物品 i 装入并达到最优状态背包容积 v 却小于这个 j 。
完全背包问题
#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);//已经优化后,朴素算法需要三重循环。
cout<<f[m]<<endl;
return 0;
}
状态表示
集合:所有只考虑第i种物品前的且总体积不大于j的所有选法。
属性:在所有集和中,价值最大的选法。
状态计算
集合的划分:总是在(第 i - 1种)状态最优时,计算第 i 个状态。
背包已经最优,故对于任意容积、前 i - 1种物品,背包总是足够满的。
当前状态 f [ i ] [ j ] 总是 f [ i - 1 ] [ j ] 和 f [ i ] [ j - v [ i ] ] 更新而来。
-
f[i][j]=f[i-1][j];
,不管容积 j 够不够,第 i 种物品还没装进去,故价值直接赋值 i - 1 的最优状态下的价值。 -
if(j<v[i])
,v [ i ] 比每一个 j 都大,装不进去。 -
if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
比较两种状态的价值,找出最优状态。
两种状态
(1)第 i 种物品被选择:
-
f[i][j]=f[i][j-v[i]]+w[i];
。由f[i][j]=f[i-1][j-k*v[i]]+k*w[i];
推导而来。 -
f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i]);
背包有空间,剩余容积足够,直接装入 k 个第i种物品,价值更新。 - 推导:
f[i][j-v[i]]=max(f[i-1][j-v],f[i-1][j-k*v[i]]+(k-1)*w[i]);
f[i][j-v[i]]+w[i]=max(f[i-1][j-v]+w[i],f[i-1][j-k*v[i]]+k*w[i]);
f[i][j-v[i]]+w[i]=max(f[i-1][j-k*v[i]]+k*w[i]);
f[i][j]=f[i][j-v[i]]+w[i];
(2)第 i 种物品未被选择:
-
f[i][j]=f[i-1][j];
背包有空间,但剩余容积不够,装不进去,价值不变。
只有这一段代码和01背包不同:文章来源:https://www.toymoban.com/news/detail-788297.html
for(int j=v[i];j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
原因是当前状态 f [ i ] [ j ] 总是 f [ i - 1 ] [ j ] 和 f [ i ] [ j - v [ i ] ] 更新而来 ,两种状态均是上一次更新的最优状态。文章来源地址https://www.toymoban.com/news/detail-788297.html
到了这里,关于【笔记】动态规划(1)---01背包和完全背包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!