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

背包问题全类型背包问题 给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。 背包问题⼤体都可以⽤上述⽅式进⾏描述，但在具体的问题上有了不同的限制条件，于是便有了各种类型的背包问题。背包问题可基本分为0-1背包问题、部分背包问题、多重背包问题、完全背包问题四⼤类。接下 从四种问题的解决的核⼼算法可以把部分背包问题单独化为⼀类，其核⼼算法为贪⼼。其余的三种背包问题都可以⽤动态规划解决。造成部分背包问题与其他的背包问题最⼤不同的原因是其限定条件的不同，部分1. 部分背包问题限定条件： 每件物品可以只选取⼀部分完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品可以进⾏分割，分割后的价值按取⾛重量占该物品总重量的⽐值计算。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 贪⼼分析： 根据本题的特殊性，我们可以任意地对某⼀部品进⾏分割，所以我们优先选择性价⽐⾼的物品，即单位重量下物品的价值。解题代码//C++#include#include#includeusing namespace std;struct bag { int w,v; //w表⽰重量 v表⽰价值 double p; //⽤来储存v/w 性价⽐}a[10005];bool cmp(bag x,bag y) { return x.p > y.p; //性价⽐⾼的物品排在前⾯}int main() {剩余 } } printf('%.2fn', ans); //输出答案 return 0;}注意计算时注意数据类型 在计算“性价⽐”的时候要注意，在C/C++等⼀部分语⾔中存在以下机制 int/int = int ，这样是⽆法计算出⼩数的，需要将其中任意⼀项浮点化即可。2. 0-1背包问题限定条件： 每件物品有且仅有⼀件完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品有且只有⼀件。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 递归、动态规划分析： 物品不可进⾏分割，不可再像部分背包问题⼀样选择性价⽐⾼的物品。举个例⼦，背包容量为10物品重量价值性价⽐A8162B7121.71C351.67若按照性价⽐回西安选择物品A，此时⽆法再选择物品B或物品C，背包总价值为16。但如果我们选择物品B和物品C，背包的价值为17，后者更优。 每件物品只有选择或不选择两种状态，这像极了⼆进制的0和1，选择即1不选即0，故得名0-1背包问题。 我们先来说说递归算法，通过反复的递与归模拟每件物品选与不选两种状态最后算出最优解。不难得出时间复杂度为O(N^2)。 这样⼤的时间复杂度在物品数量较多时⽆法⾼效的完成计算。我们需要⼀种更为⾼效的算法——动态规划。动态规划可以在O(N*C)的时间复杂度下完成计算，其基本思想是令表⽰在前个物品中能够装⼊容量为的背递归代码递归代码//c++#include#include#define MAXN 10005using namespace std;int n,c,u[MAXN],v[MAXN]; //n-物品数量 c-背包容量 u[i]第i件物品的重量 v[i]第i件物品的价值 int ans; //答案//dfs参数含义 void dfs(当前物品编号，已选中物品重量总和，已选动态规划代码//c++#include#includeusing namespace std;int n,c; //n-物品总数 c-背包容量 int w,v; //w-物品重量 v-物品价值 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d',&w,&v); for(int j = 1; j <= c; j++)

当然，0-1背包问题还有许多优秀的算法可以解决，如记忆化搜索等等。选择了递归和动态规划是因为递归最为简单，⽽动态规划解法为后⾯两个背包问题进⾏了铺垫。记忆化搜索确实是⼀门很实⽤的算法，在思维程3.完全背包问题限定条件： 每件物品都有⽆限个完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且没见物品有⽆限多个。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 动态规划分析： 和0-1背包问题对⽐⼀下，不难发现不同的地⽅在于0-1背包问题中，每件物品每件物品最多只能选择⼀次，⽽在完全背包问题中，每件物品可以选择任意件。 试着在0-1背包问题的状态转移⽅程的基础上进dp[i][j] = max(f[i-1][j-k*u[i]]+k*w[i]) 其中，0<=k*u[i]<=c解题代码//c++#include#includeusing namespace std;int n,c; //n-物品总数 c-背包容量 int w,v; //w-当前物品重量 v-当前物品价值 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d',&w,&v); for(int j = 1; j <= c;4. 多重背包问题限定条件： 每件物品有有限个完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，有 p[i] 件。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 动态规划分析： 和0-1背包问题和完全背包问题对⽐⼀下，不难发现不同的地⽅在于多重背包问题可以选择多个，但⼜不能超过某种限制，这种限制就是每件物品的个数是⼀定的，所以我们只需要在循环⾥加⼊这种限制就可解题代码

//c++#include#includeusing namespace std;int n,c; //n-物品总数 c-背包容量 int w,v,p; //w-物品重量 v-物品价值 p-物品个数 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d%d',&w,&v,&p);到这⾥背包问题的四种类型就介绍完了，最后感谢⼤家的关注，让你们久等了！

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

背包问题全类型背包问题 给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。 背包问题⼤体都可以⽤上述⽅式进⾏描述，但在具体的问题上有了不同的限制条件，于是便有了各种类型的背包问题。背包问题可基本分为0-1背包问题、部分背包问题、多重背包问题、完全背包问题四⼤类。接下 从四种问题的解决的核⼼算法可以把部分背包问题单独化为⼀类，其核⼼算法为贪⼼。其余的三种背包问题都可以⽤动态规划解决。造成部分背包问题与其他的背包问题最⼤不同的原因是其限定条件的不同，部分1. 部分背包问题限定条件： 每件物品可以只选取⼀部分完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品可以进⾏分割，分割后的价值按取⾛重量占该物品总重量的⽐值计算。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 贪⼼分析： 根据本题的特殊性，我们可以任意地对某⼀部品进⾏分割，所以我们优先选择性价⽐⾼的物品，即单位重量下物品的价值。解题代码//C++#include#include#includeusing namespace std;struct bag { int w,v; //w表⽰重量 v表⽰价值 double p; //⽤来储存v/w 性价⽐}a[10005];bool cmp(bag x,bag y) { return x.p > y.p; //性价⽐⾼的物品排在前⾯}int main() {剩余 } } printf('%.2fn', ans); //输出答案 return 0;}注意计算时注意数据类型 在计算“性价⽐”的时候要注意，在C/C++等⼀部分语⾔中存在以下机制 int/int = int ，这样是⽆法计算出⼩数的，需要将其中任意⼀项浮点化即可。2. 0-1背包问题限定条件： 每件物品有且仅有⼀件完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品有且只有⼀件。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 递归、动态规划分析： 物品不可进⾏分割，不可再像部分背包问题⼀样选择性价⽐⾼的物品。举个例⼦，背包容量为10物品重量价值性价⽐A8162B7121.71C351.67若按照性价⽐回西安选择物品A，此时⽆法再选择物品B或物品C，背包总价值为16。但如果我们选择物品B和物品C，背包的价值为17，后者更优。 每件物品只有选择或不选择两种状态，这像极了⼆进制的0和1，选择即1不选即0，故得名0-1背包问题。 我们先来说说递归算法，通过反复的递与归模拟每件物品选与不选两种状态最后算出最优解。不难得出时间复杂度为O(N^2)。 这样⼤的时间复杂度在物品数量较多时⽆法⾼效的完成计算。我们需要⼀种更为⾼效的算法——动态规划。动态规划可以在O(N*C)的时间复杂度下完成计算，其基本思想是令表⽰在前个物品中能够装⼊容量为的背递归代码递归代码//c++#include#include#define MAXN 10005using namespace std;int n,c,u[MAXN],v[MAXN]; //n-物品数量 c-背包容量 u[i]第i件物品的重量 v[i]第i件物品的价值 int ans; //答案//dfs参数含义 void dfs(当前物品编号，已选中物品重量总和，已选动态规划代码//c++#include#includeusing namespace std;int n,c; //n-物品总数 c-背包容量 int w,v; //w-物品重量 v-物品价值 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d',&w,&v); for(int j = 1; j <= c; j++)

当然，0-1背包问题还有许多优秀的算法可以解决，如记忆化搜索等等。选择了递归和动态规划是因为递归最为简单，⽽动态规划解法为后⾯两个背包问题进⾏了铺垫。记忆化搜索确实是⼀门很实⽤的算法，在思维程3.完全背包问题限定条件： 每件物品都有⽆限个完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且没见物品有⽆限多个。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 动态规划分析： 和0-1背包问题对⽐⼀下，不难发现不同的地⽅在于0-1背包问题中，每件物品每件物品最多只能选择⼀次，⽽在完全背包问题中，每件物品可以选择任意件。 试着在0-1背包问题的状态转移⽅程的基础上进dp[i][j] = max(f[i-1][j-k*u[i]]+k*w[i]) 其中，0<=k*u[i]<=c解题代码//c++#include#includeusing namespace std;int n,c; //n-物品总数 c-背包容量 int w,v; //w-当前物品重量 v-当前物品价值 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d',&w,&v); for(int j = 1; j <= c;4. 多重背包问题限定条件： 每件物品有有限个完整问题描述： 有 n 件物品，第i件物品重 w[i]，价值为 v[i]，有 p[i] 件。在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法： 动态规划分析： 和0-1背包问题和完全背包问题对⽐⼀下，不难发现不同的地⽅在于多重背包问题可以选择多个，但⼜不能超过某种限制，这种限制就是每件物品的个数是⼀定的，所以我们只需要在循环⾥加⼊这种限制就可解题代码

//c++#include#includeusing namespace std;int n,c; //n-物品总数 c-背包容量 int w,v,p; //w-物品重量 v-物品价值 p-物品个数 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d%d',&w,&v,&p);到这⾥背包问题的四种类型就介绍完了，最后感谢⼤家的关注，让你们久等了！