2023年8月1日发(作者：)
背包问题的各种求解⽅法⼀、“0-1背包”问题描述： 给定n中物品，物品i的重量是wi，其价值为vi，背包的容量为c.问应如何选择装⼊背包中的物品，使得装⼊背包中的物品的总价值最⼤？ 形式化描述：给定c>0,wi>0,vi>0,1≤i≤n，要求找⼀个n元0-1向量（x1,x2,...,xn)，xi∈{0,1}，1≤i≤n，使得∑wixi≤c，⽽且∑vixi达到最⼤。因此0-1背包问题是⼀个特殊的整形规划问题： max ∑vixi s.t ∑wixi≤c xi∈{0,1}，1≤i≤n⼆、动态规划求解（两种⽅法，顺序或逆序法求解） 1.最优⼦结构性质 1.1 简要描述 顺序：将背包物品依次从1,2,...n编号，令i是容量为c共有n个物品的0-1背包问题最优解S的最⾼编号。则S'=S-{i}⼀定是容量为c-wi且有1,...,i-1项物品的最优解。如若不是，领S''为⼦问题最优解，则V(S''+{i})>V(S'+{i})，⽭盾。这⾥V(S)=V(S')+vi. 逆序：令i是相应问题最优解的最低编号，类似可得。 1.2 数学形式化语⾔形式化的最优⼦结构 顺序（从前往后）：设(y1,y2,...,yn)是所给问题的⼀个最优解。则(y1,...,yn-1)是下⾯相应⼦问题的⼀个最优解： max ∑vixi s.t ∑wixi≤c xi∈{0,1}，1≤i≤n-1如若不然，设(z1,...,zn-1)是上述⼦问题的⼀个最优解，⽽(y1,...,yn-1)不是它的最优解。由此可知，∑vizi>∑viyi,且∑vizi+wnyn≤c。因此 ∑viyi+vnyn>∑viyi(前⼀个范围是1~n-1，后⼀个是1~n) ∑vizi+wnyn≤c这说明(z1,z2,...,yn)是⼀个所给问题的更优解，从⽽(y1,y2,...,yn)不是问题的所给问题的最优解，⽭盾。 逆序：同样的，是设(y2,...,yn)是相应⼦问题的最优解，其他类似。 2、阶段决策过程描述（动态规划的标准形式，这⾥⽤顺序法表⽰） 2.1 共有n个阶段，阶段k=1,2,...,n，每个阶段便是需要作出⼀个决策的⼦问题部分。这⾥相当于可以将背包问题分解为n个⼦问题。 2.2 状态与状态变量xk：表⽰第k阶段背包的容量 2.3 决策变量uk：表⽰k阶段是否取物品k，即uk(xk)∈{0,1}，是⼀个符号函数。 2.4 状态转移⽅程：xk+1 = xk+uk(xk)*xk 2.5 指标函数和最优指标函数，指标函数：衡量决策过程策略的优劣程度、数量指标。定义在全过程上的指标函数记为V1,k(或Vk,n，此时是逆序)，有 V1,k=V1,k(x0,x1,u1,...,xk) 最优指标函数：当指标函数达到最优值时称其为最优指标函数，记为fk(xk).它表⽰从第初始状态x1起到状态xk过程（或xk→xn，逆‘序)，采取最优策略时得到的指标函数值，如下所⽰： fk(xk)=opt V1,k 此处的最优指标函数值fk(xk)：表⽰共有1,2,...,k个物品背包容量为xk的最优值如下： 为了便于编程实现，⽤m[i,j]表⽰fk(xk)，表⽰背包容量为j，可选择物品为1,2,...,i时0-1背包问题的最优解。则可得公式如下： 第1个公式表⽰初始值（边界条件，令其为0）或者背包容量为0则结果也为0，第2个公式表⽰物品i的重量⼤于背包容量不能装，第3个公式则是表⽰是否包含前物品i，前⼀个包含后⼀个不包含。 3.算法描述及其实现 3.1 ⾃底向上的⾮递归算法如下： 3.2 源码如下：
动态规划求0-1背包#include #include using namespace std;//动态规划进⾏求解得出最优值m[n][c]中相应的值void dynamic_01knap(int* w, float* v, int n, int c,vector >& m){ //最简单的背包问题递归求解，w,v分别是重量、价值数组(从0开始) //n是物品个数,c是当前背包剩余的容量 //m是额外的表，存储相应的最优值 int i = 0, j = 0; for (; j <= c; ++j) m[0][j] = 0;//边界值 for (i = 1; i <= n; ++i) { m[i][0] = 0;//背包容量为空时 for (j = 1; j <= c; ++j){ if (w[i-1] <= j) //记住v,w是从0开始的 m[i][j] = m[i-1][j-w[i-1]]+v[i-1] > m[i-1][j] ? m[i-1][j-w[i-1]]+v[i-1] : m[i-1][j]; else m[i][j] = m[i-1][j]; cout << "m[" << i <<"][" << j << "]=" << m[i][j] << endl;//测试 } }}//找出相应的结果x[n]void traceback(int* w,float* v, int n,int c,vector >& m, vector& x){ //x是求解向量 int i = 0; for (i = n-1; i > 0; --i) { cout << "m[" << i <<"][" << c << "]=" << m[i][c] << //测试 ";m[" << i+1 <<"][" << c << "]=" << m[i+1][c] << endl; if (m[i][c] == m[i+1][c])//不取物品i+1,记住从0开始的 x[i] = false; else //取物品i+1，背包容量变⼩ { x[i] = true; c -= w[i]; } } x[0] = m[n][c] ? true : false;}int main(){ int w[] = {10, 20, 30}, c = 50, i = 0, n = sizeof(w)/sizeof(w[0]); float v[] = {60, 100, 120}; vector > m(n+1, vector(c+1)); vector x(n); dynamic_01knap(w,v,n,c,m); traceback(w,v,n,c,m,x); for (; i < n; ++i) cout << x[i] <<' '; cout << endl;} 注意，这⾥⽤的是顺序法，即最优值为m[n][c]，所以在输出0-1数组（结果）的时候得从后往前输；相反的，如果⽤逆序法，这最优值为m[1][c]，输出的时候则是从前往后输。 3.3 ⾃顶向下的递归算法-做备忘录法（memoization） memorized-0-1-knapsack(v, w, n, c)for i = 1 to n //初始化赋值为∞ for j = 1 to c m[i][j] = ∞; return lookup_max(v,w,n,c);
lookup_max(v, w, i, j)if m[i][j] < ∞ return m[i][j]if i == 0 || j ==0 m[i][j] = 0;if w[i] <= j m[i][j] = lookup_max(v,w,i-1,j-w[i])+v[i] > lookup_max(v,w,i-1,j] ?
lookup_max(v,w,i-1,j-w[i])+ v[i] : lookup_max(v,w,i-1,j];else m[i][j] = lookup_max(v,w,i-1,j];return m[i][j];
3.5 复杂度分析两种⽅法的优劣⽐较 两种算法的空间复杂度是⼀样的，都是O(nc)，时间复杂度数量级上也是⼀样的，也为O(nc)，但是因为背包问题有些⼦问题并不需要求解，所以第⼆种⽅法将第⼀种⽅法。 另外，上述⽅法有两个明显的缺点： (1) 算法要求所给物品的重量是整数，⽽递归式中并⽆这要求； (2) 当背包容量很⼤时，算法要求的计算时间较多。例如当c>2n时，需要Ω(n2n)。 针对这两种情况，可以适当的改进，改进算法略；⼆、回溯法求解 1. 回溯法的基本思想 回溯法是⼀种穷举搜索⽅法，在明确问题的解空间（该问题解的所有情况，包括⼀些不满⾜要求的解）后，将解空间组织成数或图的形式，数的叶⼦结点的个数即是所有解的个数。 然后从开始结点（根结点）出发，以深度优先的⽅式搜索整个解空间。这个开始结点就成为⼀个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深⽅向移到⼀个新节点处。这个新节点就成为⼀个新的活结点，并成为当前扩展结点。 如果在当前的扩展结点处不能再向纵深⽅向移动，则当前的扩展结点就成为死结点。此时，应往回移动（回溯）⾄最近的⼀个活动结点处，并使这个货结点成为当前的扩展结点。回溯法即以这种⽅式递归地在解空间中搜索，直到找到所求的解或解空间已⽆或结点为⽌。 在⽤回溯法搜索解空间树时，通常采⽤两种策略（加上剪枝函数）来避免⽆效搜索，提⾼搜索效率： 1）⽤约束函数在扩展结点处减去不满⾜约束的⼦树； 2）⽤限界函数减去不能得到最优解的⼦树。 回溯法有两种基本形式：递归回溯和迭代回溯（这两种⽅法可以互相转换，因为⼀般回溯法的递归回溯是尾递归，所以迭代回溯⼀般也不⽤⽤栈）。 ⽤回溯法解题的⼀个显著特征是问题的解空间是在搜索过程中动态产⽣的。在任何时刻，算法之保存从根结点到当前扩展结点的路径。如果解空间中从根结点到叶⼦结点的最长路径长度为h(n)，则回溯法所需的计算空间通常为O(h(n))，另外回溯法的时间复杂度为叶⼦结点的个数。 解空间⼀般有两种形式： 1）⼦集树：所给问题是从n个元素的集合s中找出满⾜某种性质的⼦集时，相应的解空间树。相当于求结合s的幂集。这类⼦集树通常有2n个叶⼦结点，其结点总个数为2n+1-1，时间复杂度为Ω(2n); 2）排列数：同理，所给问题是确定n个元素满⾜某种性质的排列时的相应的解空间。遍历排列数通常需要Ω(n!). 2. 背包问题的回溯法求解 2.1 基本思路 显然可以⽤⼦集树表⽰其解空间，解的所有可能情况。⽤可⾏性约束减去不满⾜约束的⼦树，⽤上界函数剪去不能得到最优解的⼦树。 2.2 源程序如下：回溯法求0-1背包问题#include #include #include using namespace std;class Goods{public: int id; float v;//商品价值 float w; //商品重量 float p; //商品单价 bool operator <= (Goods G) const { return (p >= G.p); }};class Knap{ friend float knapsack(vector Gs, float c,int n);//返回最优装载重量private: float bound(int i); //计算上界 void backtrack(int i); int n; //物品数 vector goods; //物品数组 float c,//背包容量 cw, //当前重量 cp, //当前价值 bestp; //当前最优价值 bool *x, //当前解 *bestx; //当前最优解};float Knap::bound(int i){ float cleft = c - cw;//剩余背包容量 float b = cp; //假设物品已经按单位重量价值递减排序装⼊物品 while (i n) //到达叶⼦结点 { if (cp >bestp) { bestp = cp; for (int j = 0; j < n; ++j) bestx[j] = x[j]; } return; } if(cw + goods[i-1].w <= c) //x[i] = 1搜索左⼦树 { x[i-1] = true; cw += goods[i-1].w; cp += goods[i-1].v; backtrack(i+1); //返回⾄该结点 cw -= goods[i-1].w; cp -= goods[i-1].v; } if (bound(i+1) > bestp) //x[i] = 0搜索右⼦树 { x[i-1] = false; backtrack(i+1); }}bool Upgreater ( Goods g1, Goods g2 ){ return (g1<=g2);}float knapsack(vector Gs, float c,int n) //返回最优装载重量{ //为Knap::backtrck初始化 int i = 0; float W = 0, P = 0; Knap K; = Gs; for (i = 0; i < n; ++i) { P += Gs[i].p; W += Gs[i].w; } if (W <= c) //装⼊所有物品 return P; sort((),(),Upgreater); = 0; = 0; K.c = c; K.n = n; = 0; K.x = new bool[n]; = new bool[n]; //回溯搜索 ack(1); cout << "装载情况为：" << endl; for (i = 0; i < n; ++i) cout << "物品id=" << [i].id <<":" << [i] << endl; delete[] K.x; delete[] ; return ;}int main(){ int n = 4, i =0; float c = 7, bestp, w[] = {3, 5, 2, 1}, v[] = {9, 10, 7, 4}; vector Gs(n); for (i = 0; i < n; ++i) { Gs[i].id = i+1; Gs[i].w = w[i]; Gs[i].v = v[i]; Gs[i].p = v[i]/w[i]; } bestp = knapsack(Gs,c,n); cout << "该背包的最优装载价值为：" << bestp << endl; return 0;}
2023年8月1日发(作者：)
背包问题的各种求解⽅法⼀、“0-1背包”问题描述： 给定n中物品，物品i的重量是wi，其价值为vi，背包的容量为c.问应如何选择装⼊背包中的物品，使得装⼊背包中的物品的总价值最⼤？ 形式化描述：给定c>0,wi>0,vi>0,1≤i≤n，要求找⼀个n元0-1向量（x1,x2,...,xn)，xi∈{0,1}，1≤i≤n，使得∑wixi≤c，⽽且∑vixi达到最⼤。因此0-1背包问题是⼀个特殊的整形规划问题： max ∑vixi s.t ∑wixi≤c xi∈{0,1}，1≤i≤n⼆、动态规划求解（两种⽅法，顺序或逆序法求解） 1.最优⼦结构性质 1.1 简要描述 顺序：将背包物品依次从1,2,...n编号，令i是容量为c共有n个物品的0-1背包问题最优解S的最⾼编号。则S'=S-{i}⼀定是容量为c-wi且有1,...,i-1项物品的最优解。如若不是，领S''为⼦问题最优解，则V(S''+{i})>V(S'+{i})，⽭盾。这⾥V(S)=V(S')+vi. 逆序：令i是相应问题最优解的最低编号，类似可得。 1.2 数学形式化语⾔形式化的最优⼦结构 顺序（从前往后）：设(y1,y2,...,yn)是所给问题的⼀个最优解。则(y1,...,yn-1)是下⾯相应⼦问题的⼀个最优解： max ∑vixi s.t ∑wixi≤c xi∈{0,1}，1≤i≤n-1如若不然，设(z1,...,zn-1)是上述⼦问题的⼀个最优解，⽽(y1,...,yn-1)不是它的最优解。由此可知，∑vizi>∑viyi,且∑vizi+wnyn≤c。因此 ∑viyi+vnyn>∑viyi(前⼀个范围是1~n-1，后⼀个是1~n) ∑vizi+wnyn≤c这说明(z1,z2,...,yn)是⼀个所给问题的更优解，从⽽(y1,y2,...,yn)不是问题的所给问题的最优解，⽭盾。 逆序：同样的，是设(y2,...,yn)是相应⼦问题的最优解，其他类似。 2、阶段决策过程描述（动态规划的标准形式，这⾥⽤顺序法表⽰） 2.1 共有n个阶段，阶段k=1,2,...,n，每个阶段便是需要作出⼀个决策的⼦问题部分。这⾥相当于可以将背包问题分解为n个⼦问题。 2.2 状态与状态变量xk：表⽰第k阶段背包的容量 2.3 决策变量uk：表⽰k阶段是否取物品k，即uk(xk)∈{0,1}，是⼀个符号函数。 2.4 状态转移⽅程：xk+1 = xk+uk(xk)*xk 2.5 指标函数和最优指标函数，指标函数：衡量决策过程策略的优劣程度、数量指标。定义在全过程上的指标函数记为V1,k(或Vk,n，此时是逆序)，有 V1,k=V1,k(x0,x1,u1,...,xk) 最优指标函数：当指标函数达到最优值时称其为最优指标函数，记为fk(xk).它表⽰从第初始状态x1起到状态xk过程（或xk→xn，逆‘序)，采取最优策略时得到的指标函数值，如下所⽰： fk(xk)=opt V1,k 此处的最优指标函数值fk(xk)：表⽰共有1,2,...,k个物品背包容量为xk的最优值如下： 为了便于编程实现，⽤m[i,j]表⽰fk(xk)，表⽰背包容量为j，可选择物品为1,2,...,i时0-1背包问题的最优解。则可得公式如下： 第1个公式表⽰初始值（边界条件，令其为0）或者背包容量为0则结果也为0，第2个公式表⽰物品i的重量⼤于背包容量不能装，第3个公式则是表⽰是否包含前物品i，前⼀个包含后⼀个不包含。 3.算法描述及其实现 3.1 ⾃底向上的⾮递归算法如下： 3.2 源码如下：
动态规划求0-1背包#include #include using namespace std;//动态规划进⾏求解得出最优值m[n][c]中相应的值void dynamic_01knap(int* w, float* v, int n, int c,vector >& m){ //最简单的背包问题递归求解，w,v分别是重量、价值数组(从0开始) //n是物品个数,c是当前背包剩余的容量 //m是额外的表，存储相应的最优值 int i = 0, j = 0; for (; j <= c; ++j) m[0][j] = 0;//边界值 for (i = 1; i <= n; ++i) { m[i][0] = 0;//背包容量为空时 for (j = 1; j <= c; ++j){ if (w[i-1] <= j) //记住v,w是从0开始的 m[i][j] = m[i-1][j-w[i-1]]+v[i-1] > m[i-1][j] ? m[i-1][j-w[i-1]]+v[i-1] : m[i-1][j]; else m[i][j] = m[i-1][j]; cout << "m[" << i <<"][" << j << "]=" << m[i][j] << endl;//测试 } }}//找出相应的结果x[n]void traceback(int* w,float* v, int n,int c,vector >& m, vector& x){ //x是求解向量 int i = 0; for (i = n-1; i > 0; --i) { cout << "m[" << i <<"][" << c << "]=" << m[i][c] << //测试 ";m[" << i+1 <<"][" << c << "]=" << m[i+1][c] << endl; if (m[i][c] == m[i+1][c])//不取物品i+1,记住从0开始的 x[i] = false; else //取物品i+1，背包容量变⼩ { x[i] = true; c -= w[i]; } } x[0] = m[n][c] ? true : false;}int main(){ int w[] = {10, 20, 30}, c = 50, i = 0, n = sizeof(w)/sizeof(w[0]); float v[] = {60, 100, 120}; vector > m(n+1, vector(c+1)); vector x(n); dynamic_01knap(w,v,n,c,m); traceback(w,v,n,c,m,x); for (; i < n; ++i) cout << x[i] <<' '; cout << endl;} 注意，这⾥⽤的是顺序法，即最优值为m[n][c]，所以在输出0-1数组（结果）的时候得从后往前输；相反的，如果⽤逆序法，这最优值为m[1][c]，输出的时候则是从前往后输。 3.3 ⾃顶向下的递归算法-做备忘录法（memoization） memorized-0-1-knapsack(v, w, n, c)for i = 1 to n //初始化赋值为∞ for j = 1 to c m[i][j] = ∞; return lookup_max(v,w,n,c);
lookup_max(v, w, i, j)if m[i][j] < ∞ return m[i][j]if i == 0 || j ==0 m[i][j] = 0;if w[i] <= j m[i][j] = lookup_max(v,w,i-1,j-w[i])+v[i] > lookup_max(v,w,i-1,j] ?
lookup_max(v,w,i-1,j-w[i])+ v[i] : lookup_max(v,w,i-1,j];else m[i][j] = lookup_max(v,w,i-1,j];return m[i][j];
3.5 复杂度分析两种⽅法的优劣⽐较 两种算法的空间复杂度是⼀样的，都是O(nc)，时间复杂度数量级上也是⼀样的，也为O(nc)，但是因为背包问题有些⼦问题并不需要求解，所以第⼆种⽅法将第⼀种⽅法。 另外，上述⽅法有两个明显的缺点： (1) 算法要求所给物品的重量是整数，⽽递归式中并⽆这要求； (2) 当背包容量很⼤时，算法要求的计算时间较多。例如当c>2n时，需要Ω(n2n)。 针对这两种情况，可以适当的改进，改进算法略；⼆、回溯法求解 1. 回溯法的基本思想 回溯法是⼀种穷举搜索⽅法，在明确问题的解空间（该问题解的所有情况，包括⼀些不满⾜要求的解）后，将解空间组织成数或图的形式，数的叶⼦结点的个数即是所有解的个数。 然后从开始结点（根结点）出发，以深度优先的⽅式搜索整个解空间。这个开始结点就成为⼀个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深⽅向移到⼀个新节点处。这个新节点就成为⼀个新的活结点，并成为当前扩展结点。 如果在当前的扩展结点处不能再向纵深⽅向移动，则当前的扩展结点就成为死结点。此时，应往回移动（回溯）⾄最近的⼀个活动结点处，并使这个货结点成为当前的扩展结点。回溯法即以这种⽅式递归地在解空间中搜索，直到找到所求的解或解空间已⽆或结点为⽌。 在⽤回溯法搜索解空间树时，通常采⽤两种策略（加上剪枝函数）来避免⽆效搜索，提⾼搜索效率： 1）⽤约束函数在扩展结点处减去不满⾜约束的⼦树； 2）⽤限界函数减去不能得到最优解的⼦树。 回溯法有两种基本形式：递归回溯和迭代回溯（这两种⽅法可以互相转换，因为⼀般回溯法的递归回溯是尾递归，所以迭代回溯⼀般也不⽤⽤栈）。 ⽤回溯法解题的⼀个显著特征是问题的解空间是在搜索过程中动态产⽣的。在任何时刻，算法之保存从根结点到当前扩展结点的路径。如果解空间中从根结点到叶⼦结点的最长路径长度为h(n)，则回溯法所需的计算空间通常为O(h(n))，另外回溯法的时间复杂度为叶⼦结点的个数。 解空间⼀般有两种形式： 1）⼦集树：所给问题是从n个元素的集合s中找出满⾜某种性质的⼦集时，相应的解空间树。相当于求结合s的幂集。这类⼦集树通常有2n个叶⼦结点，其结点总个数为2n+1-1，时间复杂度为Ω(2n); 2）排列数：同理，所给问题是确定n个元素满⾜某种性质的排列时的相应的解空间。遍历排列数通常需要Ω(n!). 2. 背包问题的回溯法求解 2.1 基本思路 显然可以⽤⼦集树表⽰其解空间，解的所有可能情况。⽤可⾏性约束减去不满⾜约束的⼦树，⽤上界函数剪去不能得到最优解的⼦树。 2.2 源程序如下：回溯法求0-1背包问题#include #include #include using namespace std;class Goods{public: int id; float v;//商品价值 float w; //商品重量 float p; //商品单价 bool operator <= (Goods G) const { return (p >= G.p); }};class Knap{ friend float knapsack(vector Gs, float c,int n);//返回最优装载重量private: float bound(int i); //计算上界 void backtrack(int i); int n; //物品数 vector goods; //物品数组 float c,//背包容量 cw, //当前重量 cp, //当前价值 bestp; //当前最优价值 bool *x, //当前解 *bestx; //当前最优解};float Knap::bound(int i){ float cleft = c - cw;//剩余背包容量 float b = cp; //假设物品已经按单位重量价值递减排序装⼊物品 while (i n) //到达叶⼦结点 { if (cp >bestp) { bestp = cp; for (int j = 0; j < n; ++j) bestx[j] = x[j]; } return; } if(cw + goods[i-1].w <= c) //x[i] = 1搜索左⼦树 { x[i-1] = true; cw += goods[i-1].w; cp += goods[i-1].v; backtrack(i+1); //返回⾄该结点 cw -= goods[i-1].w; cp -= goods[i-1].v; } if (bound(i+1) > bestp) //x[i] = 0搜索右⼦树 { x[i-1] = false; backtrack(i+1); }}bool Upgreater ( Goods g1, Goods g2 ){ return (g1<=g2);}float knapsack(vector Gs, float c,int n) //返回最优装载重量{ //为Knap::backtrck初始化 int i = 0; float W = 0, P = 0; Knap K; = Gs; for (i = 0; i < n; ++i) { P += Gs[i].p; W += Gs[i].w; } if (W <= c) //装⼊所有物品 return P; sort((),(),Upgreater); = 0; = 0; K.c = c; K.n = n; = 0; K.x = new bool[n]; = new bool[n]; //回溯搜索 ack(1); cout << "装载情况为：" << endl; for (i = 0; i < n; ++i) cout << "物品id=" << [i].id <<":" << [i] << endl; delete[] K.x; delete[] ; return ;}int main(){ int n = 4, i =0; float c = 7, bestp, w[] = {3, 5, 2, 1}, v[] = {9, 10, 7, 4}; vector Gs(n); for (i = 0; i < n; ++i) { Gs[i].id = i+1; Gs[i].w = w[i]; Gs[i].v = v[i]; Gs[i].p = v[i]/w[i]; } bestp = knapsack(Gs,c,n); cout << "该背包的最优装载价值为：" << bestp << endl; return 0;}
发布评论