2023年8月1日发(作者：)

背包算法简介⼀、概述 动态规划（DP）算法是初学者的⼀个难点。思考DP问题时，核⼼思路仍和其它算法类似，将复杂问题分解为相对更简单的问题。简单说，⼀个问题规模N的问题是否能分解成N-1的问题（递归）？或者能否从规模1开始推导得到规模N（递推和DP）。 背包算法就是⼀种典型的从规模1推导到规模N的算法，是最常见的⼀种DP算法。它的核⼼要素有三个：背包容量，物品重量（或体积），物品价值，题⽬⼀般会要求在背包容量限制下获取最⼤价值。最简单的背包问题，有N件物品，每件物品都有⼀个重量和价值，在背包空间有限情况下如何选择物品，使得价值最⼤。 这类问题显然不能⽤贪⼼思想解决。可以把物品编号从1......N，通过从物品1开始推导的⽅式解决。（1）只有物品1，背包够⼤时最⼤价值就是物品1的价值。（2）物品2拿过来，此时背包空间够⼤显然应该拿取物品1和2，如果不够⼤就要做⼀个取舍。（3）当物品3拿过来时，此时就有4种前置状态：空包、只有物品1，只有物品2,物品1和物品2。但如果这样处理，就演变成⼀个搜索问题，复杂度为2^N。搜索算法会计算⼤量⽆效状态，效率极低。背包算法的巧妙之处在于：通过计算“不同的背包空间"下拿取前i个物品的最⼤价值，避免了⼤量⽆效的搜索，从⽽把复杂度降为N^2。 背包三要素可能表现为多种形式，⽐如背包容量是时间（以下题⽬均在洛⾕）（P1048 采药），体⼒（P1510 精卫填海），数值（P1734 最⼤约数和）。物品重量和背包容量在同⼀题⽬中的概念总是⼀致的。 背包问题主要有四种基础类型：01背包、完全背包、分组背包、多重背包。在此之上有针对背包容量进⾏升级的⼆维背包（有两个不同的容量限制）、有针对物品种类进⾏升级的混合背包（⽐如有些物品01，有些物品多重），有存在依赖关系的背包，⽐如拿B物品必须拿A物品。 从本⽂作者的经验看，只要掌握了01背包的⼆维写法，其他所有背包问题都可以通过此算法扩展出来。换句话说，所有的背包问题都是01背包的拓展。⽐如说有依赖关系的物品A和B（拿B必须拿A），可以想象成是两件物品做01背包，⼀件是A，⼀件是（A+B）。⼆、01背包 01背包指的是n个物品都是唯⼀的，我们对每⼀件物品只有选择或者不选择两种操作。01背包是所有其他背包问题的基础。通过转换思维⽅式，可以⽤01背包的⼆维数组解法解出所有的背包问题。 01背包的基础作法与其他动规类题⽬类似，每⼀次循环完成⼀个物品的计算⼯作。⽤⼆维数组dp[i][j]表⽰拿完第i件物品时j背包容量的最⼤值或⽅案数。 在物品价值⽅⾯，如果题⽬给了价值或者价值计算⽅法（P1060 开⼼的⾦明），那么我们写dp⽅程时按题⽬要求添加即可。如果没有给物品价值，只是让我们求能填充的最⼤容量或者求⽅案数，我们可以将dp数组的0号单元置1，dp[0]=1,便于推导最⼤容量或⽅案数。#include using namespace std;int t,m,dp[105][1005],ti[105],val[105];int main(){ int i,j; cin>>t>>m; for(i=1; i<=m; i++) cin>>ti[i]>>val[i]; for(i=1; i<=m; i++) { for(j=0; j<=t; j++) { if(j

dp[i][j]=dp[i-1][j]; else /**< dp[i-1][j]不选择i物品，dp[i-1][j-ti[i]]+val[i]选择 */ dp[i][j]=max(dp[i-1][j],dp[i-1][j-ti[i]]+val[i]); } } cout<using namespace std;int t,m,dp[1005],ti[105],val[105];int main(){ int i,j; cin>>t>>m; for(i=1; i<=m; i++) cin>>ti[i]>>val[i]; for(i=1; i<=m; i++)/**< 特别注意滚动的⽅向必须从⼤到⼩ */ for(j=t; j>=ti[i]; j--) /**< dp[j]不选择i物品,dp[j-ti[i]]+val[i]选择i */ dp[j]=max(dp[j],dp[j-ti[i]]+val[i]); cout<using namespace std;int i,j,T,M,t[101],p[101],dp[101][1001];int main(){ scanf("%d%d",&T,&M); for(i=1;i<=M;i++) scanf("%d%d",&t[i],&p[i]); for(i=1;i<=M;i++) { for(j=0;j

printf("%d",f[M][T]); return 0;} 对于背包问题的代码理解，个⼈建议每次背包计算之后都输出dp数组，观察dp数组变化的过程。从上⾯代码看很明显每次dp[i][j]都先从dp[i-1][j]获取值，因此完全背包同样可以使⽤⼀维数组滚动计算，此时正好和01背包循环次序相反。#include using namespace std;int v,t,m,dp[100005],ti[10005],val[10005];int main() /**< P1616 疯狂的采药 */{ int i,j; cin>>t>>m; for(i=1; i<=m; i++) cin>>ti[i]>>val[i]; for(i=1; i<=m; i++) /**< 为实现1件，2件....t/ti件物品，完全背包从⼩到⼤滚动 */ for(j=ti[i]; j<=t; j++) dp[j]=max(dp[j],dp[j-ti[i]]+val[i]); cout<using namespace std; /**< ⼀本通1272：【例9.16】分组背包 */int v,n,t,a[1005],b[1005],c[1005],f[15][205];int main(){ int i,j,k,minn=INT_MAX; cin>>v>>n>>t; for(i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i]; for(i=1; i<=t; i++) /**< 分组的01背包，⼀组⼀组拿 */ { for(j=v; j>=0; j--) f[i][j]=f[i-1][j];/**< 初始化第k组价值为前⼀组，有可能这⼀组不能拿物品（价值太低） */ for(k=1; k<=n; k++) /**< 循环n件物品 */ if(c[k]==i) /**< 物品属于第i组 */ for(j=v; j>=a[k]; j--) /**< ⽤第i件物品去试探能否获得更⼤价值 */ f[i][j]=max(f[i][j],f[i-1][j-a[k]]+b[k]); } cout<using namespace std;int n,m,dp[100005],a[10005],b[10005],c[10005];int main() /**< P1757 通天之分组背包，80分代码 */{ int i,j,k; cin>>m>>n; for(i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i]; for(k=1; k<=n; k++) /**< k表⽰组号 */ for(j=m;j>=0;j--) /**< 对于每⼀个dp[j]，我们⽤k组的全部物品计算 因为是01背包，切记j必须从⼤到⼩*/ for(i=1;i<=n;i++) if(c[i]==k&&a[i]<=j) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); cout<

#include using namespace std;int n,m,a[1005],dp[1005];int main() /**< P1077 摆花 */{ cin>>n>>m; int i,j,k; for(i=1; i<=n; i++) cin>>a[i]; dp[0]=1; for(i=1; i<=n; i++) /**< i件物品 */ { for(j=m; j>=0; j--) { /**< 认为第i种物品拿ai盆属于不同的物品 */ for(k=1;k<=a[i]&&k<=j;k++) dp[j]=(dp[j]+dp[j-k])%1000007; } } cout<

2023年8月1日发(作者：)

背包算法简介⼀、概述 动态规划（DP）算法是初学者的⼀个难点。思考DP问题时，核⼼思路仍和其它算法类似，将复杂问题分解为相对更简单的问题。简单说，⼀个问题规模N的问题是否能分解成N-1的问题（递归）？或者能否从规模1开始推导得到规模N（递推和DP）。 背包算法就是⼀种典型的从规模1推导到规模N的算法，是最常见的⼀种DP算法。它的核⼼要素有三个：背包容量，物品重量（或体积），物品价值，题⽬⼀般会要求在背包容量限制下获取最⼤价值。最简单的背包问题，有N件物品，每件物品都有⼀个重量和价值，在背包空间有限情况下如何选择物品，使得价值最⼤。 这类问题显然不能⽤贪⼼思想解决。可以把物品编号从1......N，通过从物品1开始推导的⽅式解决。（1）只有物品1，背包够⼤时最⼤价值就是物品1的价值。（2）物品2拿过来，此时背包空间够⼤显然应该拿取物品1和2，如果不够⼤就要做⼀个取舍。（3）当物品3拿过来时，此时就有4种前置状态：空包、只有物品1，只有物品2,物品1和物品2。但如果这样处理，就演变成⼀个搜索问题，复杂度为2^N。搜索算法会计算⼤量⽆效状态，效率极低。背包算法的巧妙之处在于：通过计算“不同的背包空间"下拿取前i个物品的最⼤价值，避免了⼤量⽆效的搜索，从⽽把复杂度降为N^2。 背包三要素可能表现为多种形式，⽐如背包容量是时间（以下题⽬均在洛⾕）（P1048 采药），体⼒（P1510 精卫填海），数值（P1734 最⼤约数和）。物品重量和背包容量在同⼀题⽬中的概念总是⼀致的。 背包问题主要有四种基础类型：01背包、完全背包、分组背包、多重背包。在此之上有针对背包容量进⾏升级的⼆维背包（有两个不同的容量限制）、有针对物品种类进⾏升级的混合背包（⽐如有些物品01，有些物品多重），有存在依赖关系的背包，⽐如拿B物品必须拿A物品。 从本⽂作者的经验看，只要掌握了01背包的⼆维写法，其他所有背包问题都可以通过此算法扩展出来。换句话说，所有的背包问题都是01背包的拓展。⽐如说有依赖关系的物品A和B（拿B必须拿A），可以想象成是两件物品做01背包，⼀件是A，⼀件是（A+B）。⼆、01背包 01背包指的是n个物品都是唯⼀的，我们对每⼀件物品只有选择或者不选择两种操作。01背包是所有其他背包问题的基础。通过转换思维⽅式，可以⽤01背包的⼆维数组解法解出所有的背包问题。 01背包的基础作法与其他动规类题⽬类似，每⼀次循环完成⼀个物品的计算⼯作。⽤⼆维数组dp[i][j]表⽰拿完第i件物品时j背包容量的最⼤值或⽅案数。 在物品价值⽅⾯，如果题⽬给了价值或者价值计算⽅法（P1060 开⼼的⾦明），那么我们写dp⽅程时按题⽬要求添加即可。如果没有给物品价值，只是让我们求能填充的最⼤容量或者求⽅案数，我们可以将dp数组的0号单元置1，dp[0]=1,便于推导最⼤容量或⽅案数。#include using namespace std;int t,m,dp[105][1005],ti[105],val[105];int main(){ int i,j; cin>>t>>m; for(i=1; i<=m; i++) cin>>ti[i]>>val[i]; for(i=1; i<=m; i++) { for(j=0; j<=t; j++) { if(j

dp[i][j]=dp[i-1][j]; else /**< dp[i-1][j]不选择i物品，dp[i-1][j-ti[i]]+val[i]选择 */ dp[i][j]=max(dp[i-1][j],dp[i-1][j-ti[i]]+val[i]); } } cout<using namespace std;int t,m,dp[1005],ti[105],val[105];int main(){ int i,j; cin>>t>>m; for(i=1; i<=m; i++) cin>>ti[i]>>val[i]; for(i=1; i<=m; i++)/**< 特别注意滚动的⽅向必须从⼤到⼩ */ for(j=t; j>=ti[i]; j--) /**< dp[j]不选择i物品,dp[j-ti[i]]+val[i]选择i */ dp[j]=max(dp[j],dp[j-ti[i]]+val[i]); cout<using namespace std;int i,j,T,M,t[101],p[101],dp[101][1001];int main(){ scanf("%d%d",&T,&M); for(i=1;i<=M;i++) scanf("%d%d",&t[i],&p[i]); for(i=1;i<=M;i++) { for(j=0;j

printf("%d",f[M][T]); return 0;} 对于背包问题的代码理解，个⼈建议每次背包计算之后都输出dp数组，观察dp数组变化的过程。从上⾯代码看很明显每次dp[i][j]都先从dp[i-1][j]获取值，因此完全背包同样可以使⽤⼀维数组滚动计算，此时正好和01背包循环次序相反。#include using namespace std;int v,t,m,dp[100005],ti[10005],val[10005];int main() /**< P1616 疯狂的采药 */{ int i,j; cin>>t>>m; for(i=1; i<=m; i++) cin>>ti[i]>>val[i]; for(i=1; i<=m; i++) /**< 为实现1件，2件....t/ti件物品，完全背包从⼩到⼤滚动 */ for(j=ti[i]; j<=t; j++) dp[j]=max(dp[j],dp[j-ti[i]]+val[i]); cout<using namespace std; /**< ⼀本通1272：【例9.16】分组背包 */int v,n,t,a[1005],b[1005],c[1005],f[15][205];int main(){ int i,j,k,minn=INT_MAX; cin>>v>>n>>t; for(i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i]; for(i=1; i<=t; i++) /**< 分组的01背包，⼀组⼀组拿 */ { for(j=v; j>=0; j--) f[i][j]=f[i-1][j];/**< 初始化第k组价值为前⼀组，有可能这⼀组不能拿物品（价值太低） */ for(k=1; k<=n; k++) /**< 循环n件物品 */ if(c[k]==i) /**< 物品属于第i组 */ for(j=v; j>=a[k]; j--) /**< ⽤第i件物品去试探能否获得更⼤价值 */ f[i][j]=max(f[i][j],f[i-1][j-a[k]]+b[k]); } cout<using namespace std;int n,m,dp[100005],a[10005],b[10005],c[10005];int main() /**< P1757 通天之分组背包，80分代码 */{ int i,j,k; cin>>m>>n; for(i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i]; for(k=1; k<=n; k++) /**< k表⽰组号 */ for(j=m;j>=0;j--) /**< 对于每⼀个dp[j]，我们⽤k组的全部物品计算 因为是01背包，切记j必须从⼤到⼩*/ for(i=1;i<=n;i++) if(c[i]==k&&a[i]<=j) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); cout<

#include using namespace std;int n,m,a[1005],dp[1005];int main() /**< P1077 摆花 */{ cin>>n>>m; int i,j,k; for(i=1; i<=n; i++) cin>>a[i]; dp[0]=1; for(i=1; i<=n; i++) /**< i件物品 */ { for(j=m; j>=0; j--) { /**< 认为第i种物品拿ai盆属于不同的物品 */ for(k=1;k<=a[i]&&k<=j;k++) dp[j]=(dp[j]+dp[j-k])%1000007; } } cout<