第三周普及一班A总结：
第九课（动态规划之01背包）：
01背包简介：
01背包是背包问题中最基础的问题。01背包的规定条件是给定几种物品,
每种物品有且只有一个（只能用一次）,并且有价值和体积两个方面。在
01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选
两种情况。如果不选择将其放入背包中,则不需要处理；如果选择将其放入
背包中,由于不知道之前放入的物品占了多大的空间,需要枚举将这个物品
放入背包后可能占背包空间的所有可能。
01背包基础代码与优化：
二维写法（优化前）：
cin>>t>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>c[i];
}
for(int i=1;i<=m;i++)
for(int j=1;j<=t;j++){
if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
else dp[i][j]=dp[i-1][j];
}
cout<<dp[m][t];
一维写法（优化后）：
cin>>t>>m;
for(int i=1;i<=t;i++){
cin>>w[i]>>c[i];
}
for(int i=1;i<=t;i++)
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
cout<<dp[m];
一维写法可以防止空间超限（MLE）。
第十课（动态规划之其他背包）：
完全背包简介：
完全背包的特点是每种物品数量没有限制，可以无限使用。全背包问题与
01背包的解法相似，状态定义也完全一致。其不同点只是次数限制方面。
基础代码：
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>c[i];
}
for(int i=1;i<=m;i++)
for(int j=w[i];j<=n;j++){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
cout<<dp[n];
注意：01背包的循环变量j为递减计算，而完全背包是递增计算。
多重背包简介：
与01背包相似，有规定次数限制，每样物品可以取x次。包括01背包也能够
想成次数为1的多重背包来计算。
基础代码：
for(int j=v;j>=w[i];j--)
for(int k=1;k<=p[i] and k*w[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
sum=max(sum,dp[j]);
}
cout<<sum;
混合背包简介：
将01背包，完全背包，多重背包组合成的多样性背包问题。因为01背包可以看作
特殊的多重背包，所以可以忽略不写。
基础代码：
cin>>v>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>c[i]>>p[i];
for(int i=1;i<=n;i++){
if(p[i]==0)
for(int j=w[i];j<=v;j++){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
sum=max(sum,dp[j]);
}
else
for(int j=v;j>=w[i];j--)
for(int k=1;k<=p[i] and k*w[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
sum=max(sum,dp[j]);
}
}
cout<<sum;
分组背包简介：
分组背包是01背包的一种变形。分组背包中物品被分成几组，每组中只能挑选出
一件物品加入背包，这是与01背包的区别。
基础代码：
cin>>m>>n>>t;
for (int i=1;i<=n;i++){
cin>>a>>b>>c;
v[c].push_back(b);
w[c].push_back(a);
}
for (int i=1;i<=t;i++){
for (int j=m;j>=0;j--){
for (int k=0;k<w[i].size();k++){
if(j>=w[i][k]){
dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
}
}
}
}
cout<<dp[m];
第十一课（线性动态规划）：
最长上升子序列（LIS）：
对于一个数的序列bi，当b1<b2<...<bS的时候，我们称这个序列是上升的。
对于给定的一个序列(a1,a2,...,an)，我们可以找到一些上升的子序列(ai1
,ai2,...,aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(
1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等
等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
基础代码：
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],1+dp[j]);
}
}
sum=max(sum,dp[i]);
}
cout<<sum;
最长公共子序列（LCS）：
最长公共子序列（LCS）是一个在一个序列集合中用来查找所有序列中最长子序列的问题。
基础代码：
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],1+dp[j]);
}
}
sum=max(sum,dp[i]);
}
cout<<sum;
3 个赞