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

c++背包九讲之完全背包⼀、背包九讲总述关于动态规划问题，最典型的就是背包九讲，先理解背包九讲后再总结关于动态规划的问题。1、01背包问题2、完全背包问题3、多重背包问题4、混合背包问题5、⼆维费⽤的背包问题6、分组背包问题7、背包问题求⽅案数8、求背包问题的⽅案9、有依赖的背包问题上⼀个博客讲解了⼆、完全背包问题完全背包问题: 有n件物品和⼀个容量为C的背包， 每种物品有⽆数件，第i件物品的费⽤是w[i]，价值是v[i]。求解将哪些物品装⼊背包可使价值总和最⼤。对于第i件物品，依旧存在两种情况：1、第i件选择不放进背包时：V[i][j]=V[i-1][j];此时总价值就是只有i-1个物体，背包容量为j时，可获得的最⼤价值总和2、第i件选择放进背包时：V[i][j]=V[i][j-w[i]]+v[i];这⾥是和01背包问题的区别所在，因为完全背包问题是存在⽆数件相同的物体，故第i件放进背包⾥之后还可能再把它放进背包⾥，所以此时是V[i][j]=V[i][j-w[i]]+v[i]，不是V[i][j]=V[i-1][j-w[i]]+v[i]拿01背包博客的⽰例2举例：#include#includeusing namespace std;//全局变量定义在堆区，⾃动初始化int V[100][100];int x[100];int packet(int n, int C, int v[], int w[]){ int i = 0, j = 0; //此循环为核⼼，重点！！ for (i = 0; i <= n; i++) { for (j = 1; j <= C; j++) { if (j < w[i]) { V[i][j] = V[i - 1][j]; } else V[i][j] = max(V[i - 1][j], V[i][j - w[i]] + v[i]); } } cout << "最⼤价值："<> n; cout << "输⼊背包容量" << endl; cin >> C; cout << "输⼊各个物品的价值" << endl; for (int i = 1; i <= n; i++) { cin >> v[i]; } cout << "输⼊各个物品的重量" << endl; for (int i = 1; i <= n; i++) { cin >> w[i]; } packet(n, C, v, w); while (1);}也进⼀步升华（O(VN)的算法）：上⾯使⽤⼆维数组来记录每⼀个状态，⼈们追求更好的⽅法，即使⽤滚动数组来优化空间，⽤⼀维数组来实现：⼆维数组实现：V[i][j] = max(V[i - 1][j ], V[i][j - w[i]] + v[i])⼀维数组实现：V[j] = max(V[j], V[j - w[i]] + v[i])可以发现，这与01背包问题的递推公式完全相同，但是区别在哪⾥呢？？那就是01背包问题是采⽤逆序，对于完全背包问题必须采⽤顺序。#include#includeusing namespace std;//全局变量定义在堆区，⾃动初始化int V[100];int packet(int n, int C, int v[], int w[]){ int i = 0, j = 0; //此循环为核⼼，重点！！ for (i = 0; i <= n; i++) { //滚动数组优化空间，顺序 for (j = 1; j <= C; j++) { if (j < w[i]) { V[j] = V[j]; } else V[j] = max(V[j], V[j - w[i]] + v[i]); } } cout << V[C] << endl; return 0;}int main(){ int n; //输⼊的物品个数 int C; //最⼤的容量 int v[100] = { 0 }; //第i个物品的价值 int w[100] = { 0 }; //第i个物品的重量 cout << "输⼊物品个数" << endl; cin >> n; cout << "输⼊背包容量" << endl; cin >> C; cout << "输⼊各个物品的价值" << endl; for (int i = 1; i <= n; i++) { cin >> v[i]; } cout << "输⼊各个物品的重量" << endl; for (int i = 1; i <= n; i++) { cin >> w[i]; } packet(n, C, v, w); while (1);}

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

c++背包九讲之完全背包⼀、背包九讲总述关于动态规划问题，最典型的就是背包九讲，先理解背包九讲后再总结关于动态规划的问题。1、01背包问题2、完全背包问题3、多重背包问题4、混合背包问题5、⼆维费⽤的背包问题6、分组背包问题7、背包问题求⽅案数8、求背包问题的⽅案9、有依赖的背包问题上⼀个博客讲解了⼆、完全背包问题完全背包问题: 有n件物品和⼀个容量为C的背包， 每种物品有⽆数件，第i件物品的费⽤是w[i]，价值是v[i]。求解将哪些物品装⼊背包可使价值总和最⼤。对于第i件物品，依旧存在两种情况：1、第i件选择不放进背包时：V[i][j]=V[i-1][j];此时总价值就是只有i-1个物体，背包容量为j时，可获得的最⼤价值总和2、第i件选择放进背包时：V[i][j]=V[i][j-w[i]]+v[i];这⾥是和01背包问题的区别所在，因为完全背包问题是存在⽆数件相同的物体，故第i件放进背包⾥之后还可能再把它放进背包⾥，所以此时是V[i][j]=V[i][j-w[i]]+v[i]，不是V[i][j]=V[i-1][j-w[i]]+v[i]拿01背包博客的⽰例2举例：#include#includeusing namespace std;//全局变量定义在堆区，⾃动初始化int V[100][100];int x[100];int packet(int n, int C, int v[], int w[]){ int i = 0, j = 0; //此循环为核⼼，重点！！ for (i = 0; i <= n; i++) { for (j = 1; j <= C; j++) { if (j < w[i]) { V[i][j] = V[i - 1][j]; } else V[i][j] = max(V[i - 1][j], V[i][j - w[i]] + v[i]); } } cout << "最⼤价值："<> n; cout << "输⼊背包容量" << endl; cin >> C; cout << "输⼊各个物品的价值" << endl; for (int i = 1; i <= n; i++) { cin >> v[i]; } cout << "输⼊各个物品的重量" << endl; for (int i = 1; i <= n; i++) { cin >> w[i]; } packet(n, C, v, w); while (1);}也进⼀步升华（O(VN)的算法）：上⾯使⽤⼆维数组来记录每⼀个状态，⼈们追求更好的⽅法，即使⽤滚动数组来优化空间，⽤⼀维数组来实现：⼆维数组实现：V[i][j] = max(V[i - 1][j ], V[i][j - w[i]] + v[i])⼀维数组实现：V[j] = max(V[j], V[j - w[i]] + v[i])可以发现，这与01背包问题的递推公式完全相同，但是区别在哪⾥呢？？那就是01背包问题是采⽤逆序，对于完全背包问题必须采⽤顺序。#include#includeusing namespace std;//全局变量定义在堆区，⾃动初始化int V[100];int packet(int n, int C, int v[], int w[]){ int i = 0, j = 0; //此循环为核⼼，重点！！ for (i = 0; i <= n; i++) { //滚动数组优化空间，顺序 for (j = 1; j <= C; j++) { if (j < w[i]) { V[j] = V[j]; } else V[j] = max(V[j], V[j - w[i]] + v[i]); } } cout << V[C] << endl; return 0;}int main(){ int n; //输⼊的物品个数 int C; //最⼤的容量 int v[100] = { 0 }; //第i个物品的价值 int w[100] = { 0 }; //第i个物品的重量 cout << "输⼊物品个数" << endl; cin >> n; cout << "输⼊背包容量" << endl; cin >> C; cout << "输⼊各个物品的价值" << endl; for (int i = 1; i <= n; i++) { cin >> v[i]; } cout << "输⼊各个物品的重量" << endl; for (int i = 1; i <= n; i++) { cin >> w[i]; } packet(n, C, v, w); while (1);}