0-1背包问题的多种解法

一、 问题描述0/1背包问题:现有n 种物品，对1<=i<=n ，已知第i 种物品的重量为正整数W i ，价值为正整数V i ，背包能承受的最大载重量为正整数W ，现要求找出这n 种物品的一个子集，使得子集中物品的总重量不超过W 且总价值尽量大。

（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）二、 算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：)2(max )1()1}(1,0{11∑∑==⎪⎩⎪⎨⎧≤≤∈≤ni i i ini i i x v n i x Wx w 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量),......,,,(321n x x x x X =。

首先说明一下0-1背包问题拥有最优解。

假设),......,,,(321n x x x x 是所给的问题的一个最优解，则),......,,(32n x x x 是下面问题的一个最优解：∑∑==⎪⎩⎪⎨⎧≤≤∈-≤ni i i ini i i x v n i x x w W x w 2211max )2}(1,0{。

如果不是的话，设),......,,(32n y y y 是这个问题的一个最优解，则∑∑==>n i ni ii ii xv y v 22，且∑=≤+ni iiW yw x w 211。

因此，∑∑∑====+>+ni i i n i n i i i i i x v x v x v y v x v 1221111，这说明),........,,,(321n y y y x 是所给的0-1背包问题比),........,,,(321n x x x x 更优的解，从而与假设矛盾。

穷举法：用穷举法解决0-1背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。

消 费 电子 Байду номын сангаас
２ ０ １ ３年 １ ０月下 Ｃ ｏ ｎ ｓ ｕ ｍｅ ｒ Ｅ ｌ ｅ ｃ ｔ ｒ ｏ ｎ ｉ ｃ ｓ Ｍａ ｇ ａ ｚ ｉ ｎ ｅ 技 术 交 流
浅谈 ０ － １ 背包问题的常用算法
汤赫 男
（ 吉林工商学院信息工程学院，长春 １ ３ ０ ０ ６ ２） 摘 要 ：０ －１ 背 包问题是典型的 ＮＰ ～完全问题 ，无论从 理论 上还是 实践上都有一定的研究意义。本文综述 了几 种０ — １背包问题的 常用算法 ，分析算法的优劣 ，预 测 ０ － １背包问题的发展方向。 关键 词 ：０ — １背包问题 ；动 态规划法 ；贪心法 ；分支界限法
一
、
∑ｗ ，
ｌ ｛
㈠ ｛ “ ｝ ｍ ａ ｘ ∑
｛ ｊ
二 、常用 的 ０ － １ 背 包问题算法 （ 一） 蛮力法。 蛮 力法又称穷举法或枚举法，是一种简单、 直接、有效的方法，是初学者入 门的方法 。蛮力法要求遍历所 有可能情 况一次且仅一次 ，筛选 出符合要求 的解。应用蛮力法 求解 ０ － １ 背包 问题， 需要考虑给定的 ｎ 个物品集合的所有子集， 找出所有总重量不超过背包容量的子集 ，计算每个可能子集的 总价值，然后找 出价值最大的子集 。对于一个具有 ｎ个元素的 集合 ，其子集数量是 ２ “，所 以，不论生成子集 的算法效率有 多高 ，蛮力法求解 ０ － １ 背包 问题都会导致一个 Ｑ （ ２ ｎ ）的算法 。 （ 二 ）动 态规划法。动态规划 法是一种通用 的算 法设计 技术用来求解 多阶段决策最优 化问题。这类 问题都满 足最优 性原理，即原 问题 的最优 性包含着子 问题 的最优性 。 应用 动态规划法 求解 ０ － １ 背包 问题 ，可 以将 ０ — １背包 问 题看 作一个 多阶段决策最 优化 问题 。ｎ个物 品集合 的所 有子 集可 以看 作该 问题 的所有 可行解；这些可行解 都是满足约束 条件 的，可行解可能不止一个，通过 目标 函数找到最优解 。 动态 规划 法求解 ０ － １ 背包 问题 的算法描述 ： 设Ｖ （ ｎ ， Ｃ ）表 示将 ｎ个 物 品装入 容量 为 Ｃ的背 包获 得 的 最大价值 。 初 始 状 态 ：Ｖ （ ｉ ， ０ ） ＝ Ｖ （ ０ ， ｊ ） ＝ ０ ， ０≤ ｉ ≤ｎ ， ０≤ ｊ≤ Ｃ 则Ｖ （ ｉ ， ｊ ）表示 将前 ｉ 个 物 品装入 容量 为 ｊ的背 包获 得

实验四“0-1”背包问题一、实验目的与要求熟悉C/C++语言的集成开发环境：通过本实验加深对贪心算法、动态规划算法的理解。

二、实验内容：掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析貝优缺点。

三、实验题1.“0-1”背包问题的贪心算法2.“0-1”背包问题的动态规划算法说明：背包实例采用教材P132习题六的6-1中的描述。

要求每种的算法都给出最大收益和最优解。

设有背包问题实例n=7, M=15,, (w0,wl,…w6)= (2, 3, 5, 7,1,4,1),物品装入背包的收益为:(p0, pl,。

，p6) = (10,5,15,7,6,18,3)。

求这一实例的最优解和最大收益。

四、实验步骤理解算法思想和问题要求；编程实现题目要求：上机输入和调试自己所编的程序：验证分析实验结果；整理岀实验报告。

五、实验程序//贪心法求解#i nclude 〈iostream> #include ，/iomanip // using namespace std;//按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的 数组，运用冒泡排序void AvgBenefitsSort (float *arry_avgp, float *arry_p, float *arry_w ); /7获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物 品最优解的数组和还可以装载物品的重量float GetBestBenifit (float *arry_p,float *arry_w, float*arry_x, float u);int main() {float w[7] = {2, 3, 5, 7, 1, 4, 1}; float p[7] = {10, 5, 15, 7, 6, 18, 3}; float avgp[7]={0);float x[7]二{0}; const float M=15; float ben=0; AvgBenefitsSort(avgp, p, w); ben=GetBestBenif it (p, w, x, M);cout«endK<ben«endl; /,/输 L L I M 后的收益system ("pause"); return 0;}//按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序void AvgBenefitsSort (float *arry_avgp, float *arry_p, float *arry_w ) {//求岀物品的单位收益for (int i=0;i<7;i++){arry_avgp[i]=arry_p[i]/arry_w[i];} cout«endl;//把求出的单位收益排序，冒泡排序法int exchange 二7;int bound=0;float temp=0; //物品重量数组//物品收益数组//单位毒品的收益数组//最后装载物品的最优解数组 //背包所能的载重//最后的收益while(exchange)bound=exchange; exchange二0;for (int i=0;i<bound;i++){if (arry_avgp[i]<arry_avgp[i+1]) {〃交换单位收益数组temp=arry_avgp[i];arry_avgp[i]=arry_avgp[i+1]; arry_avgp[i+1]=temp;//交艇收益数组temp=arry_p[i];arry_p[i]=arry_p[i+1]; arry_p[i+l]=temp;//交换重量数组temp=arry_w[i]; arry_w[i]=arry_w[i+1];arry_w[i+1]二t emp;exchange=i;}}}}//获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit (float *arry_p, float *arry_w, float *arry_x, float u){int i二0; ,7循坏变量ifloat benifit=0; //最后收益while (i<7){if(u~arry_w[i]>0){arry.X[i]=a rry_w[i]; //把半前物品重量缴入最优解数组benif it+=arry_p[i]; //收益增加前物品收益u-=arry_w[i]: //背包还能载逼量减去前物品巫cout«arry_x[i]//输出最优解} i++；}return benifit; //返回最后收益}//动态规划法求解nclude〈>#include<>#define n 6void DKNAP(int p[], int w[], int M, const int m): void main(){int p[n+l], w[n+l];int M, i, j；int m^l;for(i=l;i<=n;i++){m=m*2;printf C\nin put the weight and the p:〃)；scanf (，z%d %d", &w[i], &p[i]);)printf (，z%d/z, m);printf (，z\n in put the max weight H:〃)；scanf("%d", &M);DKNAP (p, w, M, m);}void DKNAP(int p[], int w[], int M, const int m){int p2[m], w2[m], pp, ww, px;int F[n+1], pk, q, k, 1, h, u, i, j, next, max, s[n+l];F[0]二1;p2[l]=w2[l]=0;l=h=l;F[l]二next二2;for(i=l;i<n;i 卄){k二1;max=0;u 二1;for (q=l;q<=h;q++)if ((w2 [q]+w[i] <=M) &&max<=w2 [q] +w [ i ]){u二q;max=w2[q] +w[i]；}for(j=l;j<=u;j++){PP二p2[j]+p[i]；ww二w2[j]+w[i];while(k<=h&&w2[k]〈ww) {p2[next]=p2[k];w2[next]=w2[k];next++;k++;}辻(k<=h&&w2[k]二二ww){if(pp<=p2[k])pp二p2 [k];k++;}else if(pp>p2[next-1]){p2[next]=pp;w2[next]=ww;next++;}while (k<=h&&p2[k]<=p2[next-1])k++;}while(k<=h){p2[next]=p2[k];w2[next]二w2[k];next二next+1; k++;}1二h+1;h二next-1;F[i+1]二next;}for(i=l;i<next;i++)printf C%2d%2d ", p2[i], w2[i]); for (i=n;i>0;i一一)next二F[i];next一一；pp=pk=p2[next];ww=w2[next];while (ww+w[i] >M&&next>F[iT])next=next~l; pp=p2[next]; ww二w2[next];}if(ww+w[i]<=M&&next>F[i -1]) px=pp+p[i];if(px>pk&&ww+w[i]<=M){s[i]二1; M=M-w[i]; printf (z，M=%d ",M);}else s[i]二0;)for (i=l;i<=n;i++)printf("%2d",s[i]);)六、实验结果1.贪心法截图:七、实验分析。

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

注：0/1背包问题：给定种物品和一个容量为的背包，物品的重n C i 量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装i w i v 入背包中的物品的总价值最大。

其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n 种可选物品的0/1背包问题，其解空间由长度为n 的0-1向量组成,可用子集数表示。

在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2）代码:#include<iostream>#include<algorithm>using namespace std;#define N 100//最多可能物体数struct goods //物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];/*蛮力法求解0/1背包问题*/int Force(int i){if(i>n-1){if(bestP<cp&&cw+a[i].w<=C){for (int k=0;k<n;k++)X[k]=cx[k];//存储最优路径bestP=cp;}return bestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1;//装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0;//不装入背包Force(i+1);return bestP;}int KnapSack1(int n,goods a[],int C,int x[]){Force(0);return bestP;}int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i<n;i++)//输入物品i 的重量w 及其价值v {printf("物品%d 的重量w[%d]及其价值v[%d]:",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf("蛮力法求解0/1背包问题:\nX=[ ");for(i=0;i<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("]装入总价值%d\n",sum1);bestP=0,cp=0,cw=0;//恢复初始化}3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：。

、问题描述0/1背包问题：现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W,价值为正整数V，背包能承受的最大载重量为正整数V，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。

(注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分)、算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：nw i x i Wi i ⑴X i {0,1(1 i n)nmax v i x (2)i 1于是，问题就归结为寻找一个满足约束条件( 1)，并使目标函数式(2)达到最大的解向量首先说明一下0-1背包问题拥有最优解假设(X1, X2,X3,……,X n)是所给的问题的一个最优解，则 (X2,X3,……,X n)是下面问题的一个最优解:nWi 2X i {0,1}(2W1X1 maxi n) inv i X。

如果不是的话，设(y2> y3>....2..,y n)是这个问题的一个最优解，则n nV i y i V i X ii 2 i 2，且 W1X1n nW i y i W。

因此，V1X1 V i y ii 2 i 2n nV1X1V j X VX i，这说明i 2 i 1(X1,y2,y3, ....... , y n)是所给的0-1背包问题比(X1,X2,X3, ............ , X n)更优的解，从而与假设矛盾穷举法:用穷举法解决0-1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集(总重量不超过背包重量的子集)，计算每个子集的总重量，然后在他们中找到价值最大的子集。

由于精品(X1, X2,X3,……X n)。

程序过于简单，在这里就不再给出，用实例说明求解过程。

下面给出了4个物品和一个容量为10的背包，下图就是用穷举法求解0-1背包问题的过程。

(a)四个物品和一个容量为10的背包(b)用回溯法求解0-1背包问题的过程递归法：在利用递归法解决0-1背包问题时，我们可以先从第n个物品看起。

0-1背包问题是一种常见的动态规划问题，其目标是在给定背包容量和物品集合的情况下，选择某些物品放入背包，使得背包内物品的总价值最大。

以下是求解0-1背包问题的算法综述：
1. 定义变量和参数：
* 物品集合：包括每个物品的重量和价值。

* 背包容量：表示背包能够容纳的最大重量。

* dp数组：用于存储每个状态下的最大价值，dp[i][j]表示前i个物品、背包承重为j时的最大价值。

2. 初始化dp数组：
* 对于每个物品i和背包容量j，如果物品i能够装入背包，则令dp[i][j]为0；否则，令dp[i][j]为负无穷。

3. 递推计算dp数组：
* 对于每个物品i和背包容量j，如果物品i能够装入背包，则令dp[i][j]为当前物品的价值加上前i-1个物品、背包容量为j-w[i]时的最大价值，即dp[i][j] = dp[i-1][j-w[i]] + p[i]；否则，
令dp[i][j]为前i-1个物品、背包容量为j时的最大价值，即dp[i][j] = dp[i-1][j]。

4. 返回dp数组的最后一个元素，即为所求的最大价值。

以上是求解0-1背包问题的算法综述，实际实现时可以根据具体情况进行优化，以提高算法的效率和性能。

０ — １背包 问题 的解 决 方法 多 种 多样 ，常用 的算法 有贪 心算 法 、 回溯法 、 分 枝一限界法 等 。本文 采用 动态
规 划 原理 来 求 解 ０ 一 ｌ背 包 问题 也不 失 为 一 种 简单 明 了、 清 晰 易懂 的方法 。 参考 文献 ：
［ １ ］ 王 晓东． 计算机 算法设计与分析 ［ Ｍ］ ． 北京： 电子 工业 出版社
ｗ ｈ ｉ ｌ ｅ（ ｍ【 ｉ Ⅱ ｃ 】 ＝ ＝ ｍ［ ｉ 一 １ ］ ［ ｃ ］ ） ｉ － － ； ｗ ｈ ｉ ｌ ｅ（ ｉ ＞ ０ ） ｛ ｊ ＝ ｉ 一 １ ； ｗ ｈ ｉ ｌ ｅ（ ｍ『 ｊ １ ［ ｃ ］ 一 ｍ ［ ｊ 】 【 ｃ ］ ！＝ ｖ ｉ ｉ － １ ］ ＆ ＆－ ｊ ＞ ０ ）
［ ｉ ］ ［ ｊ 】 是 下 面两 个 量 的最 大值 ： ｍ［ ｉ ＋ １ ］ ［ ｊ ］ 和 ｍ【 ｉ ＋ １ 】 【 ｊ — ｗ ［ ｉ 】
］ ＋ Ｖ 嘲
｝
｛
ｆ ｏ ｒ （ ｊ ＝ ０ ； ｊ ＜ ＝ ｃ ； ｊ ＋ ＋ ） ｐ ｒ ｉ ｎ ｔ ｆ （ ” ％３ ｄ ． ｔ ， ｍ ｆ ｉ １ 【 ｊ 】 ） ； ｐ ｉ ｆ ｎ ｆ （ ” ＼ Ｉ １ ” ） ；｝
等于 ｖ 『 ｎ １ ；
ｋ ｎ ａ ｐ ｓ ａ ｃ ｋ （ ） ；ｄ ｉ ｓ ｐ Ｏ ； ｐ ｒ ｉ ｎ ｔ ｆ （ ” 最 大价值＝ ％ｄ ＼ ｎ ” ， ｍ 【 ｎ ］ ［ ｃ 】 ） ；
ｏ ｆ ｒ （ ｉ ＿ ０ ； ｉ ＜ ＝ ｎ ； ｉ ＋ ＋ ）
②当前的背包容量 Ｊ 大于等于物品重量 ｗ ［ ｉ ］ 时， ｍ
２ ０ ０７ ．
ｉ ｎ ｔ ｎ ， Ｃ ， ｗ ［ Ｍ Ａ Ｘ ］ ， ｖ ［ ＭＡ Ｘ ］ ， ｍ ［ ＭＡ ｘ】 ［ ＭＡ ｘ 】 ＝ ｛ ０ ｝ ； ｖ ｏ ｉ ｄ ｋ ｎ ａ ｐ ｓ ａ ｃ ｋ ０ ｛ｉ ｎ ｔ ｉ ；

（0-1）背包问题的解法小结1．动态规划法递推关系：– 考虑一个由前i 个物品(1≤i ≤n )定义的实例，物品的重量分别为w 1,…,w i ，价值分别为v 1，…，v i ，背包的承重量为j (1≤j ≤W )。

设V [I,j]为该实例的最优解的物品总价值– 分成两类子集：• 根据定义，在不包括第i 个物品的子集中，最优子集的价值是V [i -1,j ]• 在包括第i 个物品的子集中(因此，j －w ≥0)，最优子集是由该物品和前i -1个物品中能够放进承重量为i －w j 的背包的最优子集组成。

这种最忧子集的总价值等于v i +V [i -1,j -w i ].0]0,[时，0 当0;][0,时，0初始条件：当],1[}],1[],,1[max{],[=≥=≥<≥⎩⎨⎧-+---=i V i j V j w j w j j i V v w j i V j i V j i V i i i i以记忆功能为基础的算法：用自顶向下的方式对给定的问题求解，另外维护一个类似自底向上动态规划算法使用的表格。

一开始的时候，用一种“null”符号创始化表中所有的单元，用来表明它们还没有被计算过。

然后，一旦需要计算一个新的值，该方法先检查表中相应的单元：如果该单元不是“null ”，它就简单地从表中取值；否则，就使用递归调用进行计算，然后把返回的结果记录在表中。

算法 MFKnapsack(I,j)//对背包问题实现记忆功能方法//输入：一个非负整数i 指出先考虑的物品数量，一个非负整数j 指出了背包的承重量 //输出：前i 个物品的最伏可行子集的价值//注意：我们把输入数组Weights[1..n],Values[1..n]和表格V[0..n,0..W]作为全局变量，除了行0和列0用0初始化以外，V 的所有单元都用-1做初始化。

if V[I,j]<01if j<Weights[i]value ←MFKnapsack(i-1,j)elsevalue ←max(MFKnapsack(i-1),j), Value[i]+MFKnapsack(i-1,j-eights[i]))V[I,j]←valuereturn V[I,j]2．贪心算法1) 背包问题基本步骤：首先计算每种物品单位重量的价值Vi/Wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

0-1背包问题计科1班朱润华 2012040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。

问题的解空间至少包含问题的一个（最优）解。

对于0-1背包问题，解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有0-1赋值。

例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为C。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。

这4个物品的单位重量价值分别为[3,2,3,5,4]。

以物品单位重量价值的递减序装入物品。

先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。

由此得一个解为[1,0.2,1,1]，其相应价值为22。

华北水利水电学院数据结构与算法分析实验报告2009 ～2010 学年第 1 学期2009 级计算机专业班级：200915326 学号：200915326 姓名：郜莉洁一、实验题目：分别用回溯法和分支限界法求解0-1背包问题二、实验内容：0-1背包问题：给定n种物品和一个背包。

物品i的重量是Wi，其价值为Vi，背包的容量为C。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。

不能将物品i装入背包多次，也不能只装入部分的物品i。

三、程序源代码：A:回溯法：// bag1.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream.h>#define MaxSize 100 //最多物品数int limitw; //限制的总重量int maxwv=0; //存放最优解的总价值int maxw;int n; //实际物品数int option[MaxSize]; // 存放最终解int op[MaxSize]; //存放临时解struct {int weight;int value;}a[MaxSize]; //存放物品数组void Knap( int i, int tw, int tv) //考虑第i个物品{int j;if(i>=n) //找到一个叶子结点{if (tw<=limitw && tv>maxwv) //找到一个满足条件地更优解，保存它{maxwv=tv; maxw=tw;for(j=0;j<n;j++) option[j]=op[j];}}else{op[i]=1; //选取第I个物品Knap(i+1,tw+a[i].weight, tv+a[i].value);op[i]=0; //不选取第I个物品，回溯Knap(i+1,tw,tv);}}int main(int argc, char* argv[]){int j;n=3; //3物品a[0].weight=16;a[0].value=45;a[1].weight=15;a[1].value=25;a[2].weight=15;a[2].value=25;//a[3].weight=1;a[3].value=1;limitw=30; //限制重量不超过30 Knap(0,0,0);cout<<"最佳装填方案是："<<endl;for(j=0;j<n;j++)if(option[j]==1)cout<<"第"<<j+1<<"种物品"<<endl;cout<<"总重量＝"<<maxw<<",总价值＝"<<maxwv<<endl;return 0;}回溯法测试结果：测试数据：物品一：重量：16，价格：45；物品二：重量：15，价格：25；物品三：重量：15，价格：25；B：分支限界法：#include <stdio.h>#include<malloc.h>#define MaxSize 100 //最多结点数typedef struct QNode{float weight;float value;int ceng;struct QNode *parent;bool leftChild;}QNode,*qnode; //存放每个结点typedef struct{qnode Q[MaxSize];int front,rear;}SqQueue; //存放结点的队列SqQueue sq;float bestv=0; //最优解int n=0; //实际物品数float w[MaxSize]; //物品的重量float v[MaxSize]; //物品的价值int bestx[MaxSize]; // 存放最优解qnode bestE;void InitQueue(SqQueue &sq ) //队列初始化{sq.front=1;sq.rear=1;}bool QueueEmpty(SqQueue sq) //队列是否为空if(sq.front==sq.rear)return true;elsereturn false;}void EnQueue(SqQueue &sq,qnode b)//入队{if(sq.front==(sq.rear+1)%MaxSize){printf("队列已满!");return ;}sq.Q[sq.rear]=b;sq.rear=(sq.rear+1)%MaxSize;}qnode DeQueue(SqQueue &sq)//出队{qnode e;if(sq.front==sq.rear){printf("队列已空!");return 0;}e=sq.Q[sq.front];sq.front=(sq.front+1)%MaxSize;return e;}void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if (i==n) //可行叶子结点{if (vt==bestv){bestE=parent;bestx[n]=(leftchild)?1:0;}return;}b=(qnode)malloc(sizeof(QNode)); //非叶子结点b->weight=wt;b->value=vt;b->ceng=i;b->parent=parent;b->leftChild=leftchild;EnQueue(sq,b);}void maxLoading(float w[],float v[],int c){float wt=0;float vt=0;int i=1; //当前的扩展结点所在的层float ew=0; //扩展节点所相应的当前载重量float ev=0; //扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); //空标志进队列while (!QueueEmpty(sq)){wt=ew+w[i];vt=ev+v[i];if (wt <= c){if(vt>bestv)bestv=vt;EnQueue1(wt,vt,i,e,true); // 左儿子结点进队列}EnQueue1(ew,ev,i,e,false); //右儿子总是可行；e=DeQueue(sq); // 取下一扩展结点if (e == NULL){if (QueueEmpty(sq)) break;EnQueue(sq,NULL); // 同层结点尾部标志e=DeQueue(sq); // 取下一扩展结点i++;}ew=e->weight; //更新当前扩展结点的值ev=e->value;}printf("最优取法为：\n");for( int j=n-1;j>0;j--) //构造最优解{bestx[j]=(bestE->leftChild?1:0);bestE=bestE->parent;}for(int k=1;k<=n;k++){if(bestx[k]==1)printf("\n物品%d:重量：%.1f，价值：%.1f\n",k,w[k],v[k]);}printf("\n");printf("最优价值为：%.1f\n\n",bestv);}void main(){int c;float ewv[MaxSize];printf(" //////////////////// 0-1背包问题分枝限界法/////////////////////\n\n");printf("请输入物品的数量：\n");scanf("%d",&n);printf("请输入背包的最大承重量：\n");scanf("%d",&c);printf("\n请输入物品的重量和单位重量价值:\n\n");for(int i=1;i<=n;i++){printf("物品%d:",i);scanf("%f%f",&w[i],&ewv[i]);v[i]=w[i]*ewv[i];printf("\n");}maxLoading(w, v, c);}分支限界法测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距，不得少于100字。

一.动态规划求解0-1背包问题/************************************************************************/ /* 0-1背包问题：/* 给定n种物品和一个背包/* 物品i的重量为wi，其价值为vi/* 背包的容量为c/* 应如何选择装入背包的物品，使得装入背包中的物品/* 的总价值最大？/* 注：在选择装入背包的物品时，对物品i只有两种选择，/* 即装入或不装入背包。

不能将物品i装入多次，也/* 不能只装入部分的物品i。

/*/* 1. 0-1背包问题的形式化描述：/* 给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的/* 0-1向量(x1, x2, ..., xn), 使得：/* max sum_{i=1 to n} (vi*xi),且满足如下约束：/* (1) sum_{i=1 to n} (wi*xi) <= c/* (2) xi∈{0, 1}, 1<=i<=n/*/* 2. 0-1背包问题的求解/* 0-1背包问题具有最优子结构性质和子问题重叠性质，适于/* 采用动态规划方法求解/*/* 2.1 最优子结构性质/* 设(y1,y2,...,yn)是给定0-1背包问题的一个最优解，则必有/* 结论，(y2,y3,...,yn)是如下子问题的一个最优解：/* max sum_{i=2 to n} (vi*xi)/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1/* (2) xi∈{0, 1}, 2<=i<=n/* 因为如若不然，则该子问题存在一个最优解(z2,z3,...,zn)，/* 而(y2,y3,...,yn)不是其最优解。

那么有：/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c/* 进一步有：/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c/* 这说明：(y1,z2,z3,...zn)是所给0-1背包问题的更优解，那么/* 说明(y1,y2,...,yn)不是问题的最优解，与前提矛盾，所以最优/* 子结构性质成立。

0-1背包问题的算法决策分析0-1背包问题是一个经典的组合优化问题，也是计算机科学和数学领域中的一个重要问题。

在实际应用中，0-1背包问题通常用于优化问题的求解，比如资源分配、货物装载等方面。

在这篇文章中，我们将对0-1背包问题的算法决策进行分析，并探讨不同算法的优缺点。

0-1背包问题的描述很简单，假设有n件物品和一个容量为W的背包。

每件物品的重量为w[i]，价值为v[i]。

现在需要选择一些物品装入背包，使得背包中的物品价值最大，同时不能超过背包的容量。

这个问题可以用一个0-1的决策变量来表示，即选择物品装入背包或者不选择。

这个问题被称为0-1背包问题。

对于0-1背包问题，有多种解法和算法可以求解。

常见的算法包括贪心算法、动态规划算法、回溯算法等。

在下面的内容中，我们将对这些算法进行具体的分析和比较。

贪心算法贪心算法是一种简单而有效的算法，它通过每一步的局部最优选择来构建全局最优解。

在0-1背包问题中，可以使用贪心算法按物品的单位价值（即每单位重量所能获得的价值）从大到小的顺序选择物品放入背包。

贪心算法的优点是简单、高效，时间复杂度低。

贪心算法并不一定能够得到最优解。

因为贪心算法只关注当前的局部最优解，而忽略了全局最优解的可能性。

在某些情况下，贪心算法无法得到最优解。

动态规划算法动态规划算法是求解0-1背包问题的经典算法之一。

动态规划算法将问题分解为子问题，并使用递推的方式求解子问题，最终得到全局最优解。

在0-1背包问题中，可以使用动态规划算法构建一个二维数组dp[i][j]，表示前i件物品在背包容量为j时所能获得的最大价值。

动态规划算法的优点是能够得到最优解，并且在一定程度上能够减小时间复杂度。

动态规划算法的空间复杂度较高，且在某些情况下需要额外的优化。

动态规划算法需要注意状态转移方程和边界条件的设计，需要一定的技巧和功底。

回溯算法回溯算法是一种穷举搜索算法，它通过遍历所有可能的解空间来求解问题。

背包问题系列算法详解背包问题是一个关于最优解的经典问题。

通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。

它是一切背包问题及相关背包问题的基础。

本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。

一、0-1背包问题有N件物品和一个容量为V的背包。

第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。

求解将哪些物品装入背包可使价值总和最大。

（1）递归求解算法如下：#include "iostream"#define CAPACITY 10#define GOODSNUM 6using namespace std;int nVol[GOODSNUM];int nValue[GOODSNUM];int knapsack(int itemIndex,int vol);void main(){int i=0,j=0;while(i<GOODSNUM){cout<<"input the "<<i+1<<"th item(volume and value):";cin>>nVol[i]>>nValue[i];i++;}cout<<"The max value is: "<<knapsack(GOODSNUM,CAPACITY)<<endl;}int knapsack(int itemIndex,int vol){if (itemIndex==0||vol==0){return 0;}else if (vol>=nVol[itemIndex] &&knapsack(itemIndex-1,vol)<knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex ]){return knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];}elsereturn knapsack(itemIndex-1,vol);}分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复计算，于是有二维数组求解。

目录一、目的与任务 (1)1.1 任务与目的 (1)1.2 开发环境 (1)1.3 参考资料 (1)1.4任务完成的一般过程 (1)1.5 个人完成的程序模块和文档清单 (1)二、程序构思、创意及改进 (1)2.1 构思 (1)2.2 创意 (2)2.3 改进 (2)三、算法流程图 (2)3.1 动态规划流程图 (2)3.2 回溯法流程图 (3)3.3 分支限界法流程图 (4)四、核心代码解释和时间复杂度分析 (4)4.1 核心代码解释 (4)4.2 时间复杂度分析 (11)五、程序运行结果 (11)5.1 程序界面 (11)5.2 动态规划方法演示 (11)5.3 回溯法演示 (13)5.4 分支限界法 (13)六、个人小结 (14)一、目的与任务1.1 任务与目的0-1背包问题描述：给定n个物品和一背包。

物品i的重量是wi ,其价值为vi ,背包的容量为C。

问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？其中要求在选择装入背包的物品时，对每种物品i只有装入背包和不装入背包两种选择。

我们将利用动态规划、回溯法和分支限界法解决0-1背包问题，从而熟悉各种算法的使用和熟悉软件底层算法及界面编程。

1.2开发环境操作系统:Windows 7编程语言：Java开发软件：eclipse1.3参考资料[1]王晓东，算法设计与分析（第二版），清华大学出版社，2008.01[2][美]John Lewis，Java程序设计教程（第六版），电子工业出版社，2010.031.4任务完成的一般过程1)选定0-1背包问题为课程设计的题目；2)先写出0-1背包问题的动态规划、回溯法和分支限界法算法；3)通过Java图形界面实现上述的各种算法。

1.5个人完成的程序模块和文档清单1)何炜洪负责动态规划、回溯法和分支限界法的算法的编写；2)谢炫楠负责各种算法的界面的实现；3)李聪负责程序的测试和文档的编写。

二、程序构思、创意及改进2.1 构思1)为何选取0-1背包为题？是因为0-1背包问题在算法这门课中反复出现，老师也介绍了几种常见的解法，对我们的启发很大，而且此问题很典型，本小组的成员对此问题比较清晰，思路较明确。

0-1背包问题的四种写法本节回顾0-1背包的基本模型，关于它的实现有很多种写法，这⾥对不同实现做个简单列举，主要是写代码练⼿了，主要有以下⼏⽅⾯内容：==0-1背包问题定义 & 基本实现==0-1背包使⽤滚动数组压缩空间==0-1背包使⽤⼀维数组==0-1背包恰好背满==0-1背包输出最优⽅案========================================0-1背包问题定义 & 基本实现问题：有个容量为V⼤⼩的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品，每种物品只有⼀个，想计算⼀下最多能放多少价值的货物。

DP的关键也是难点是找到最优⼦结构和重叠⼦问题，进⽽找到状态转移⽅程，编码就相对容易些。

最优⼦结构保证每个状态是最优的，重叠⼦问题也即n状态的求法和n-1状态的求法是⼀样的；DP在实现上⼀般是根据状态转移⽅程⾃底向上的迭代求得最优解（也可以使⽤递归⾃顶向下求解）。

回到0-1背包，每个物体i，对应着两种状态：放⼊&不放⼊背包。

背包的最优解是在⾯对每个物体时选择能够最⼤化背包价值的状态。

0-1背包的状态转移⽅程为f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }f(i,v)表⽰前i个物体⾯对容量为v时背包的最⼤价值，c[i]代表物体i的cost(即重量)，w[i]代表物体i的价值；如果第i个物体不放⼊背包，则背包的最⼤价值等于前i-1个物体⾯对容量v的最⼤价值；如果第i个物体选择放⼊，则背包的最⼤价值等于前i-1个物体⾯对容量v-cost[i]的最⼤价值加上物体i的价值w[i]。

对于实现，⼀般采⽤⼀个⼆维数组（状态转移矩阵）dp[i][j]来记录各个⼦问题的最优状态，其中dp[i][j]表⽰前i个物体⾯对容量j背包的最⼤价值。

下⾯给出0-1背包的基本实现，时间复杂度为O(N*V)，空间复杂度也为O(N*V)，初始化的合法状态很重要，对于第⼀个物体即f[0][j]，如果容量j⼩于第⼀个物体（编号为0）的重量，则背包的最⼤价值为0，如果容量j⼤于第⼀个物体的重量，则背包最⼤价值便为该物体的价值。

背包问题的各种求解⽅法⼀、“0-1背包”问题描述： 给定n中物品，物品i的重量是w i，其价值为v i，背包的容量为c.问应如何选择装⼊背包中的物品，使得装⼊背包中的物品的总价值最⼤？形式化描述：给定c>0,w i>0,v i>0,1≤i≤n，要求找⼀个n元0-1向量（x1,x2,...,x n)，x i∈{0,1}，1≤i≤n，使得∑w i x i≤c，⽽且∑v i x i达到最⼤。

因此0-1背包问题是⼀个特殊的整形规划问题：max ∑v i x is.t ∑w i x i≤cx i∈{0,1}，1≤i≤n⼆、动态规划求解（两种⽅法，顺序或逆序法求解） 1.最优⼦结构性质 1.1 简要描述 顺序：将背包物品依次从1,2,...n编号，令i是容量为c共有n个物品的0-1背包问题最优解S的最⾼编号。

则S'=S-{i}⼀定是容量为c-w i且有1,...,i-1项物品的最优解。

如若不是，领S''为⼦问题最优解，则V(S''+{i})>V(S'+{i})，⽭盾。

这⾥V(S)=V(S')+v i.逆序：令i是相应问题最优解的最低编号，类似可得。

1.2 数学形式化语⾔形式化的最优⼦结构 顺序（从前往后）：设(y1,y2,...,y n)是所给问题的⼀个最优解。

则(y1,...,y n-1)是下⾯相应⼦问题的⼀个最优解： max ∑v i x is.t ∑w i x i≤cx i∈{0,1}，1≤i≤n-1如若不然，设(z1,...,z n-1)是上述⼦问题的⼀个最优解，⽽(y1,...,y n-1)不是它的最优解。

由此可知，∑v i z i>∑v i y i,且∑v i z i+w n y n≤c。

因此∑v i y i+v n y n>∑v i y i(前⼀个范围是1~n-1，后⼀个是1~n) ∑v i z i+w n y n≤c这说明(z1,z2,...,y n)是⼀个所给问题的更优解，从⽽(y1,y2,...,y n)不是问题的所给问题的最优解，⽭盾。

一、 问题描述0/1背包问题:现有n 种物品，对1<=i<=n ，已知第i 种物品的重量为正整数W i ，价值为正整数V i ，背包能承受的最大载重量为正整数W ，现要求找出这n 种物品的一个子集，使得子集中物品的总重量不超过W 且总价值尽量大。

（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）二、 算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：)2(max )1()1}(1,0{11∑∑==⎪⎩⎪⎨⎧≤≤∈≤ni i i ini i i x v n i x Wx w 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量),......,,,(321n x x x x X =。

首先说明一下0-1背包问题拥有最优解。

假设),......,,,(321n x x x x 是所给的问题的一个最优解，则),......,,(32n x x x 是下面问题的一个最优解：∑∑==⎪⎩⎪⎨⎧≤≤∈-≤ni i i ini i i x v n i x x w W x w 2211max )2}(1,0{。

如果不是的话，设),......,,(32n y y y 是这个问题的一个最优解，则∑∑==>n i ni ii ii xv y v 22，且∑=≤+ni iiW yw x w 211。

因此，∑∑∑====+>+ni i i n i n i i i i i x v x v x v y v x v 1221111，这说明),........,,,(321n y y y x 是所给的0-1背包问题比),........,,,(321n x x x x 更优的解，从而与假设矛盾。

穷举法：用穷举法解决0-1背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。