2023年8月1日发(作者：)
【完全背包】详细解答+详细代码+⼀维数组解决+⼆维数组解决【完全背包】有n 个物品，它们有各⾃的重量和价值，现有给定容量的背包，如何让背包⾥装⼊的物品具有最⼤的价值总和？1.【题⽬描述】有n种物品和⼀个容量为v的背包，每⼀种背包⽆限使⽤，在不超过背包容量的前提下，求最⼤价值。物品3 背包容量6物品编号重量价值1232473362.【递推思路】1.【基本思路】1.确定状态变量（函数）2.确定状态转移⽅程（递推关系）3.确定边界2.【本题思路】⾸先完全背包问题和0-1背包有什么不同的地⽅呢，0-1背包每⼀件物品只能被装⼀次，完全背包就是可以⽆限制的装，物品数量没有限制。这个问题类似于01背包问题，所不同的就是每种物品⽆限制使⽤。for(int i=1;i<=n;i++) //物品
{ for(int j=1;j<=m;j++) //容量
{ if(j f[i][j]=f[i-1][j]; //就等于i-1件物品容量等于j时候的价值 else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]);//装得下分为两种情况1.装 2.不装 }}在这段代码可以看出，与0-1背包不同的地⽅是状态转移⽅程有所区别。0-1背包状态转移⽅程：f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]完全背包状态转移⽅程：f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i])当不取的时候都是⼀样的最⼤价值等于f[i-1][j]，等于i-1件物品在容量等于j的时候的最⼤值当要取的时候这⾥有不同的地⽅0-1背包是每⼀件物品只能选取⼀次 ，在解决0-1背包问题的时候我们需要找到f[i-1][j-w[i]最⼤价值。因为我们当前物品重量等于w[i]，背包总容量等于j，我们就需要找到j-w[i]容量时第i-1件物品的时候最⼤价值然后加上我们这件物品的价值。完全背包并不是找到上⼀件物品背包容量等于j-w[i]的时候，⽽是找到当前物品情况下j-w[i]的最⼤值，因为我们的物品可以⽆限制的使⽤，f[i][j-w[i]]+v[i]就是在求最⼤价值，是在放当前物品的时候容量等于j-w[i]的时候最⼤价值加上现在物品的价值，0-1背包是找到上⼀件物品背包容量等于j-w[i]的时候最⼤价值加上现在物品的价值，这就是0-1背包和完全背包不同的地⽅。3.【⼆维数组解决完全背包问题】#include int w[100];/*函数功能：求完全背包 函数形参：物品数量和背包容量函数返回值：返回最⼤值 */ int fun(int n,int m){ for(int i=1;i<=n;i++) //物品 { for(int j=1;j<=m;j++) //容量 { if(j f[i][j]=f[i-1][j]; //就等于i-1件物品容量等于j时候的价值 else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]);//装得下分为两种情况1.装 2.不装 } } return f[n][m];}int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; cout< int w[100];/*函数功能：求完全背包 函数形参：物品数量和背包容量函数返回值：返回最⼤值 */ int fun(int n,int m){ for(int i=1;i<=n;i++) //物品 { for(int j=w[i];j<=m;j++) //容量 { f[j]=max(f[j],f[j-w[i]]+v[i]);//装得下分为两种情况1.装 2.不装 } } return f[m];}int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; cout< 2023年8月1日发(作者：) 【完全背包】详细解答+详细代码+⼀维数组解决+⼆维数组解决【完全背包】有n 个物品，它们有各⾃的重量和价值，现有给定容量的背包，如何让背包⾥装⼊的物品具有最⼤的价值总和？1.【题⽬描述】有n种物品和⼀个容量为v的背包，每⼀种背包⽆限使⽤，在不超过背包容量的前提下，求最⼤价值。物品3 背包容量6物品编号重量价值1232473362.【递推思路】1.【基本思路】1.确定状态变量（函数）2.确定状态转移⽅程（递推关系）3.确定边界2.【本题思路】⾸先完全背包问题和0-1背包有什么不同的地⽅呢，0-1背包每⼀件物品只能被装⼀次，完全背包就是可以⽆限制的装，物品数量没有限制。这个问题类似于01背包问题，所不同的就是每种物品⽆限制使⽤。for(int i=1;i<=n;i++) //物品 { for(int j=1;j<=m;j++) //容量 { if(j f[i][j]=f[i-1][j]; //就等于i-1件物品容量等于j时候的价值 else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]);//装得下分为两种情况1.装 2.不装 }}在这段代码可以看出，与0-1背包不同的地⽅是状态转移⽅程有所区别。0-1背包状态转移⽅程：f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]完全背包状态转移⽅程：f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i])当不取的时候都是⼀样的最⼤价值等于f[i-1][j]，等于i-1件物品在容量等于j的时候的最⼤值当要取的时候这⾥有不同的地⽅0-1背包是每⼀件物品只能选取⼀次 ，在解决0-1背包问题的时候我们需要找到f[i-1][j-w[i]最⼤价值。因为我们当前物品重量等于w[i]，背包总容量等于j，我们就需要找到j-w[i]容量时第i-1件物品的时候最⼤价值然后加上我们这件物品的价值。完全背包并不是找到上⼀件物品背包容量等于j-w[i]的时候，⽽是找到当前物品情况下j-w[i]的最⼤值，因为我们的物品可以⽆限制的使⽤，f[i][j-w[i]]+v[i]就是在求最⼤价值，是在放当前物品的时候容量等于j-w[i]的时候最⼤价值加上现在物品的价值，0-1背包是找到上⼀件物品背包容量等于j-w[i]的时候最⼤价值加上现在物品的价值，这就是0-1背包和完全背包不同的地⽅。3.【⼆维数组解决完全背包问题】#include int w[100];/*函数功能：求完全背包 函数形参：物品数量和背包容量函数返回值：返回最⼤值 */ int fun(int n,int m){ for(int i=1;i<=n;i++) //物品 { for(int j=1;j<=m;j++) //容量 { if(j f[i][j]=f[i-1][j]; //就等于i-1件物品容量等于j时候的价值 else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]);//装得下分为两种情况1.装 2.不装 } } return f[n][m];}int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; cout< int w[100];/*函数功能：求完全背包 函数形参：物品数量和背包容量函数返回值：返回最⼤值 */ int fun(int n,int m){ for(int i=1;i<=n;i++) //物品 { for(int j=w[i];j<=m;j++) //容量 { f[j]=max(f[j],f[j-w[i]]+v[i]);//装得下分为两种情况1.装 2.不装 } } return f[m];}int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; cout<
发布评论