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

⼀本通1268：【例9.12】完全背包问题（浅谈完全背包问题）⼀道完全背包问题的模板题，和⼀样，还是拥有两种思路Solution 1依然是⼀个朴实⽆华的⼆维数组状态的表⽰：f[i][j]表⽰前i个总重量不超过j的最⼤价值状态的转移：f[i][j]=max(f[i−1][j],f[i][j−w[i]]+c[i]) (w[i]<=j)注：w[i]表⽰第i个物品的重量，c[i]表⽰第i个物品的价值，j表⽰当前的最⼤重量最优解：f[n][m]注：n指物体数量，m指最⼤重量Code#include#include#includeusing namespace std;inline void read(int &x){ int f=1; char ch=getchar(); x=0; while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f;}int m,n;int w[31],c[31];int f[201][201];int main(){ read(m);read(n); for(int i=1;i<=n;i++){ read(w[i]); read(c[i]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j

} } printf("max=%d",f[n][m]); //"max="是题⽬中的输出格式要求 return 0;}Solution 2依然可以⽤⼀维数组来进⾏空间优化状态的表⽰：f[i]表⽰不超过i重量的最⼤价值状态的转移：f[j]=max(f[j],f[j−w[i]]+c[i])注：w[i]表⽰第i个物品的重量，c[i]表⽰第i个物品的价值，j表⽰当前的最⼤重量最优解：f[m]注：m指最⼤重量Code#include#include#includeusing namespace std;inline void read(int &x){ int f=1; char ch=getchar(); x=0; while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f;}Processing math: 100%int m,n;int w[31],c[31];int f[201];int main(){ read(m);read(n); for(int i=1;i<=n;i++){ read(w[i]); read(c[i]); } for(int i=1;i<=n;i++){ for(int j=w[i];j<=m;j++){ f[j]=max(f[j],f[j-w[i]]+c[i]); } } printf("max=%d",f[m]); //"max="是题⽬中的输出格式要求 return 0;}这⾥和01背包唯⼀不同的是，内层循环变成了这个：for(int j=1;j<=m;j++)和这个for(int j=w[i];j<=m;j++)在01背包⾥，j是从最⼤重量m进⾏倒序遍历到w[i]的。⽽这⾥，是从w[i]正序遍历到最⼤重量m这便是01背包和完全背包在⼀维数组实现上的唯⼀不同之处原因还是来源于本质区别：01背包是只有选和不选两个⼦问题完全背包是有选和不选两个⼦问题，但是选⾥边还有选⼏个的若⼲⼦问题所以说，考虑“再选⼀个第i种物品”的⽅案时，有可能已经选过⼀个第i件物品，当前⾏的f[j]需要⽤到前⾯的的结果。即由于⼀个物品可以被选择多次，更新f[i][j]时，f[i][j−w[i]]可能因为放⼊物品i⽽发⽣变化。所以说需要正序循环。

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

⼀本通1268：【例9.12】完全背包问题（浅谈完全背包问题）⼀道完全背包问题的模板题，和⼀样，还是拥有两种思路Solution 1依然是⼀个朴实⽆华的⼆维数组状态的表⽰：f[i][j]表⽰前i个总重量不超过j的最⼤价值状态的转移：f[i][j]=max(f[i−1][j],f[i][j−w[i]]+c[i]) (w[i]<=j)注：w[i]表⽰第i个物品的重量，c[i]表⽰第i个物品的价值，j表⽰当前的最⼤重量最优解：f[n][m]注：n指物体数量，m指最⼤重量Code#include#include#includeusing namespace std;inline void read(int &x){ int f=1; char ch=getchar(); x=0; while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f;}int m,n;int w[31],c[31];int f[201][201];int main(){ read(m);read(n); for(int i=1;i<=n;i++){ read(w[i]); read(c[i]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j

} } printf("max=%d",f[n][m]); //"max="是题⽬中的输出格式要求 return 0;}Solution 2依然可以⽤⼀维数组来进⾏空间优化状态的表⽰：f[i]表⽰不超过i重量的最⼤价值状态的转移：f[j]=max(f[j],f[j−w[i]]+c[i])注：w[i]表⽰第i个物品的重量，c[i]表⽰第i个物品的价值，j表⽰当前的最⼤重量最优解：f[m]注：m指最⼤重量Code#include#include#includeusing namespace std;inline void read(int &x){ int f=1; char ch=getchar(); x=0; while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f;}Processing math: 100%int m,n;int w[31],c[31];int f[201];int main(){ read(m);read(n); for(int i=1;i<=n;i++){ read(w[i]); read(c[i]); } for(int i=1;i<=n;i++){ for(int j=w[i];j<=m;j++){ f[j]=max(f[j],f[j-w[i]]+c[i]); } } printf("max=%d",f[m]); //"max="是题⽬中的输出格式要求 return 0;}这⾥和01背包唯⼀不同的是，内层循环变成了这个：for(int j=1;j<=m;j++)和这个for(int j=w[i];j<=m;j++)在01背包⾥，j是从最⼤重量m进⾏倒序遍历到w[i]的。⽽这⾥，是从w[i]正序遍历到最⼤重量m这便是01背包和完全背包在⼀维数组实现上的唯⼀不同之处原因还是来源于本质区别：01背包是只有选和不选两个⼦问题完全背包是有选和不选两个⼦问题，但是选⾥边还有选⼏个的若⼲⼦问题所以说，考虑“再选⼀个第i种物品”的⽅案时，有可能已经选过⼀个第i件物品，当前⾏的f[j]需要⽤到前⾯的的结果。即由于⼀个物品可以被选择多次，更新f[i][j]时，f[i][j−w[i]]可能因为放⼊物品i⽽发⽣变化。所以说需要正序循环。