今天是放寒假的重拾算法的第二天渡过恐怖期末周后这段期间都没怎么学习编程了感觉自己又变成新兵蛋子了趁寒假时间多就多学学吧这是寒假第一篇争取寒假能写个十篇吧话不多说上干货多重背包(Ⅰ)---无优化版本以今天写的代码展开详细描述与解释,并附上题目const int N 110; int x[N], w[N], v[N];//个数重量价值 int f[N][N]; int main() { int m, n; cin m n; for (int i 1; i m; i) { cin x[i] w[i] v[i]; } for (int i 1; i m; i)//这个是种类 { for (int j n; j 0; j--)//这个是容量 { for (int k 0; k x[i] k * w[i] j; k)//k0意为可以不选 { f[i][j] max(f[i][j], f[i - 1][j - k * w[i]] k * v[i]); } } } cout f[m][n] endl; return 0; }这是一道在洛谷上写的题目所以使用全局的变量更加方便根据输入要求我直接把数组设置的足够大那么就不用考虑越界的问题题目的主要实现逻辑在于三个for循环理解每个循环的功能就能够理解其中的门道了数组xwv分别存储的是每个种类的初始数据二维数组f是用来进行动态规划的数组第一层for(i)循环是遍历一遍所有的种类第二层for(j)循环是遍历一次所有可能的容量从右往左的原因不同于完全背包完全背包可以无限制重复选择但是多重背包不行因为多重背包每个物品并没有无限个是有限的如果是从左往右遍历那么就变成了完全背包不符合题意所以从右往左遍历就可以不打破多重背包有数量限制的约束第三层for(k)循环是遍历一次每个种类所可以选的数量k需要满足条件k x[i] k * w[i] j否则就不是符合条件的情况这样可以直接剪枝减少时间复杂度k可以从0开始因为可以选择不选最后输出的f[m][n]就是所需结果多重背包(Ⅱ)---二进制优化版本这个两个版本的题目都一样就不重复展示了这里直接展示代码const int N 110 * 5;//一个物品最多20个但是可以分成五堆 //(就是五种虚拟物品并且有100个种类最多需要的位置是500个位置) //(这个是在加入x都是20的情况下) int w[N], v[N], pos 0;//重量价值 int f[N]; int main() { int n, T; cin n T; for (int i 1; i n; i) { int x, y, z; cin x y z; int t 1; while (x t) { pos; w[pos] t * y; v[pos] t * z; x - t; t * 2; } if (x) { pos; w[pos] x * y; v[pos] x * z; } } //类似01背包此时每个虚拟物品只有一个 for (int i 1; i pos; i)//遍历每个虚拟物品的重量 { for (int j T; j w[i]; j--)//寻找符合条件的重量并计算最大价值 { f[j] max(f[j], f[j - w[i]] v[i]); } } cout f[T] endl; return 0; }题目的主要实现逻辑在于理解二进制优化和模拟01背包动态规划此处我们要先理解这个原理---二进制优化一个数例如7我们二进制形式是0111即124那么在这里我们就可以把一个种类的数量划分成三堆第一堆有一个第二堆有两个第三堆有四个那么因为每一个的重量和价值都一样那么我们可以把两个和四个的集合看成一个整体设这个种类的重量为w价值为v那么两个为一个整体的话它此时的重量为2w质量为2v以此类推就是把每一个集合看成一个新的个体计算减少了时间复杂度可以转化成01背包问题再有特殊有余数的情况例20它可以写成12485因为5没办法用单独一个2的次方表示可以独立形成一个集合再进行计算统计原理就是差不多这些还不理解的话可以尝试问问豆包举例举例方便理解变量xyz是题目的源数据变量pos是用来统计把原来的种类转化成虚拟物品后有多少的个数统计常量N是用来开数组空间的为什么是550因为题目说了每个种类的物品最多有20个然后20又最多划分成5堆并且一共有100个种类以防数组越界我初始化数组都是110个所以最终由5*110个空间理解了这里差不多就知道题目的实现逻辑了第一个while循环就是统计每个种类有几个集合并且把每个集合对应的重量和价值存入w与v数组if判断在原理那一块会有像20这种数字没办法完全变成由2的次数组成的数字那么这个循环的作用就是统计余数集合的重量和价值双层for循环就是模拟01背包问题因为我们把源数据划分成了一个个的虚拟集合相当于每个虚拟集合只有一个就可以使用01背包的思维进行解答注这个二进制优化不能用于解决求方案数问题只能用于解决求最值问题因为我们集合里的物品都是同一种例如9这个数字可以分为1242如果我们 要找到符合重量为3的搭配方案(假设每个物品的重量为1)就可以把1和两个2分别搭配但是其实都是同一种情况会重复统计哇酣畅淋漓的码字希望读者可以看懂多重背包(Ⅲ)---求方案数问题以今天写的代码展开详细描述与解释,并附上题目const int N 1e6 7; const int M 110; int a[M]; int dp[M][M]; int main() { int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; } dp[0][0] 1; for (int i 1; i n; i) { for (int j m; j 0; j--) { for (int k 0; k a[i] k j; k) { dp[i][j] (dp[i][j] dp[i - 1][j - k]) % N; } } } cout dp[n][m] endl; return 0; }这是一道在洛谷上写的题目所以使用全局的变量更加方便根据输入要求我直接把数组设置的足够大那么就不用考虑越界的问题题目的主要实现逻辑在于三个for循环理解每个循环的功能就能够理解其中的门道了数组a用于存储标记每个种类不能摆放超过的数量第一层for(i)循环遍历一遍所有的种类第二层for(j)循环遍历一遍所有可能容量数第三层for(k)循环遍历这个种类所拥有的个数但是k要满足条件(k a[i] k j)否则是不符合标准的因为方案数可能很大在每次计算时我们要边求和边取模就可以保证最终的结果准确最终返回dp[n][m]的数值优化版本const int N 1e6 7; const int M 110; int a[M]; int dp[M]; int main() { int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; } dp[0] 1; for (int i 1; i n; i) { for (int j m; j 0; j--) { for (int k 1; k a[i] k j; k) { dp[j] (dp[j] dp[j - k]) % N; } } } cout dp[m] endl; return 0; }这个是空间优化的版本空间优化时我们不仅仅要修改数组的维数还要更改k的起始遍历值若k还是从0开始遍历那么就是导致重复统计dp[j]的情况导致结果错误