贪心算法和分支限界法的比较

㈠ 0/1背包问题能不能使用贪心法解决

贪心算法解决背包问题有几种策略：
(i)一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii)还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。
而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

㈡ 算法设计里面分治法、贪心法、动态规划法、回溯法、分枝限界法各是什么意思

你这个问题问的内容太多了，还是看网络吧：
分治法：http://ke..com/view/1583824.htm?fr=aladdin
贪心算法：http://ke..com/view/298415.htm
动态规划：http://ke..com/view/28146.htm
回溯算法：http://ke..com/view/6056523.htm
分支限界法：http://ke..com/view/4479359.htm

㈢ 大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

《算法分析与设计》是一门理论与应用并重的专业课程。本课程以算法设计策略为知识单元，系统介绍计算机算法的设计方法和分析技巧。课程主要内容包括:第1章，算法概述；第二章，递归和分治策略；第三章，动态规划；第四章，贪婪算法；第五章，回溯法；第六章，分枝定界法。通过介绍经典实用的算法，使学生掌握算法设计的基本方法。结合案例分析，让学生深入了解算法设计的技巧和分析算法的能力。

㈣ [算法4] 哪个算法比较难

当然是网络流啦，这个是研究生课题。。。

㈤ 编程语言中的五大经典算法的异同点！！！

这样说吧
分治和动态规划都可看成原问题由子问题合成作用而得，只不过原、子问题结构关系分别是
树型结构和有向无环图

贪心是则可看成是链式结构

回溯和分支界限为穷举式的搜索，其思想的差异是深度优先和广度优先

㈥ dijakstra算法和分支限算法在解决单源最短路径问题的异同

记dijakstra算法为D算法
D算法为贪心算法,每一步的选择为当前步的最优,复杂度为O(n*n) (又叫爬山法)
分支限界算法,每一步的扩散为当前耗散度的最优,复杂度为(没算)

都是A算法的极端情况
(说错了哈,下面我的文字中的的分支限界算法实际上是在说动态规划法,我查了一下书,动态规划法是对分支限界法的改进,分支限界法不属于A算法(启发式搜索算法),但是这时用动态规划法和D算法比较也是有可比性的,而直接用分支限界算法和D算法比较也是可以的)
关键词:耗散度 评估函数
即:对当前优先搜索方向的判断标准为,有可能的最优解
而最优解可以用一个评估函数来做,即已经有的耗散度加上以后有可能的耗度
A算法就是把两个耗散度加在一起,作为当前状态的搜索搜索方向;
但是对以后的耗散度的评估是麻烦的,D算法就是把当前有的路的最短的作为,以后耗散度的评估.
分支限界算法就是只以以前的耗散度为评估函数

你给的两个算法当然是A算法的特例
你还可以参考一下 A*算法 修正的A*算法,相信对你的编程水平有帮助

参考:
队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。按照规则，这样的结点不被列入活结点表。

优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值p来表示。最大优先队列规定p值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，体现最大效益优先的原则。类似地，最小优先队列规定p值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，体现最小优先的原则。采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的p值。

㈦ C语言常用算法分析的目录

第1篇算法基础篇
第1章程序之魂——算法
（ 自学视频、源程序：
配套资源mr1） 2
1.1魂之说 3
1.2算法的特性 4
1.3算法的表示方式 5
1.3.1用自然语言描述算法 5
1.3.2用流程图描述算法 5
1.3.3用N-S图描述算法 8
1.3.4用计算机语言描述算法 9
1.4算法性能分析与度量 10
1.4.1算法的性能指标 10
1.4.2算法效率的度量 10
1.4.3算法的时间复杂度 11
1.4.4算法的空间复杂度 12
1.5学习算法的原因 12
第2章数据结构基础
（ 自学视频、源程序：
配套资源mr2） 13
2.1数据结构概述 14
2.1.1数据结构的发展 14
2.1.2数据结构的研究对象 14
2.1.3数据结构与算法的关系 16
2.2数据结构的基本概念 16
2.3C语言常见数据结构 18
2.3.1数组 18
2.3.2结构体 20
2.3.3链表 21
2.3.4栈 23
2.3.5队列 24
第3章查找与排序算法
（ 自学视频、源程序：
配套资源mr3） 26
3.1查找算法 27
3.1.1顺序查找 27
3.1.2折半查找 29
3.1.3分块查找 31
3.1.4哈希查找 33
3.2排序算法 38
3.2.1选择排序 38
3.2.2冒泡排序 40
3.2.3直接插入排序 43
3.2.4归并排序 45
3.2.5希尔排序 48
3.2.6快速排序 49
3.2.7各种排序算法的比较 52
第4章基本算法思想
（ 自学视频、源程序：
配套资源mr4） 54
4.1递归的概念和分治法 55
4.1.1递归的概念 55
4.1.2递归的应用——汉诺塔 55
4.1.3分治法的基本思想 56
4.1.4分治法的应用——棋盘覆盖
问题 57
4.2动态规划法 59
4.2.1动态规划法的基本思想 59
4.2.2动态规划的应用——最大
子段和 60
4.3贪心算法 61
4.3.1贪心算法的基本概念 61
4.3.2贪心算法的应用——哈夫
曼编码 62
4.4回溯法 67
4.4.1回溯法的基本思想 67
4.4.2回溯法的应用——连续
邮资问题 68
4.5分支限界法 70
4.5.1分支限界法的基本思想 71
4.5.2分支限界法的应用——旅行
售货员问题 71
第2篇常用算法篇
第5章数学算法
（ 自学视频、源程序：
配套资源mr5） 76
5.1随机数求π 77
5.2正态分布的成绩 82
5.3绘制最小圆 86
5.4满意的一元二次方程解 93
5.5计算定积分 101
5.6分解质因数 103
5.7最大公约数和最小公倍数 106
5.8数字的全排列 109
5.9递推化梯形法求解定积分 111
5.10迭代法开平方运算 115
5.11牛顿切线法解方程 117
5.12改进欧拉方法求解微分方程 119
5.13迭代法求解线性方程组 123
5.14计算贷款利息 127
5.15分数计算器 129
第6章矩阵与数组问题
（ 自学视频、源程序：
配套资源mr6） 132
6.1“脱壳”组数 133
6.2寻找矩阵中的“鞍点” 135
6.3魔幻方阵 137
6.4矩阵的转置运算 139
6.5勾股数组 141
6.6百灯判熄 143
6.7巧排螺旋数阵 144
6.8猜数四问 146
第7章经典算法
（ 自学视频、源程序：
配套资源mr7） 149
7.1约瑟夫环 150
7.2八皇后问题 152
7.30-1背包问题 156
7.4斐波那契数列 159
7.5寻找水仙花数 161
7.6爱因斯坦阶梯问题 162
7.7进制转换算法 163
7.8哥德巴赫猜想 165
7.9验证四方定理 167
7.10尼科彻斯定理 168
7.11角谷猜想 170
7.12prim算法求最小生成树 171
7.13迪杰斯特拉算法 174
第3篇趣味算法篇
第8章数学趣题
（ 自学视频、源程序：
配套资源mr8） 178
8.1警察抓犯人 179
8.2舍罕王的失算 181
8.3百钱买百鸡问题 183
8.4三色球问题 185
8.5填数字游戏 187
8.6渔夫捕鱼问题 190
8.7移数字游戏 191
8.8数字翻译器 194
8.9猴子吃桃问题 198
8.10马克思手稿中的数学题 199
8.11判断回文式素数 200
8.12完全数 204
8.13自守数 206
8.14一数三平方数 207
8.15古稀数 209
8.16亲和数 213
8.17对调数 215
第9章逻辑推理题
（ 自学视频、源程序：
配套资源mr9） 218
9.1魔术师的秘密 219
9.2婚礼上的谎言 220
9.3谁讲了真话 222
9.4白纸与黑纸 223
9.5判断坏球 224
9.6打渔晒网问题 229
9.7水池注水问题 231
9.8寻找假币 232
9.9常胜将军 234
9.10巧算国王分财物 236
9.11商人渡河问题 237
9.12马踏棋盘 243
9.13猜杏核 246
第4篇算法竞技篇
第10章计算机等级考试算法实例
（ 自学视频、源程序：
配套资源mr10） 250
10.1数组的下三角置数 251
10.2查找单链表的结点 252
10.3二维数组的元素排序 254
10.4寻找二维数组的最大值 256
第11章程序员考试算法实例
（ 自学视频、源程序：
配套资源mr11） 258
11.1电话计费算法 259
11.2处理链表的重复元素 261
11.3剧场方形空位 263
11.4数组的数值操作 265
11.5三位数生成回文数 267
第12章信息学奥赛算法实例
（ 自学视频、源程序：
配套资源mr12） 269
12.1我知你心 270
12.2格雷码 272
12.3狡猾的狐狸遇上聪明的兔子 275
12.46174问题 276
12.5韩信点兵 279
12.6杨辉三角 281
12.7开关灯问题 284
12.8蛇形方阵 286

㈧ 0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）

一.动态规划求解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)不是问题的最优解，与前提矛盾，所以最优
/* 子结构性质成立。
/*
/* 2.2 子问题重叠性质
/* 设所给0-1背包问题的子问题 P(i,j)为：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 问题P(i,j)是背包容量为j、可选物品为i,i+1,...,n时的子问题
/* 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优
/* 子结构性质，可以建立m(i,j)的递归式：
/* a. 递归初始 m(n,j)
/* //背包容量为j、可选物品只有n，若背包容量j大于物品n的
/* //重量，则直接装入；否则无法装入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 递归式 m(i,j)
/* //背包容量为j、可选物品为i,i+1,...,n
/* //如果背包容量j<wi，则根本装不进物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，则在不装物品i和装入物品i之间做出选择
/* 不装物品i的最优值：m(i+1,j)
/* 装入物品i的最优值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//递归初始条件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}

for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}

//i从2到n-1，分别对j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}

m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}

}

template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}

int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;

int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}

int x[6];

Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);

return 0;
}
二.贪心算法求解0-1背包问题
1.贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1).不能保证求得的最后解是最佳的；
2).不能用来求最大或最小解问题；
3).只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；

2.例题分析

1).[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30

分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。

<程序代码:>(环境:c++)
#include<iostream.h>
#define max 100 //最多物品数
void sort (int n,float a[max],float b[max]) //按价值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1为背包剩余可装载重量
int i;
sort(n,v,w); //物品按价值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]为1时，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"请输入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品选择情况表初始化为0
cout<<"请依次输入物品的价值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"请依次输入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的总重量为："<<totalw<<endl; //背包所装载总重量
cout<<"背包的总价值为："<<totalv<<endl; //背包的总价值
}
三.回溯算法求解0-1背包问题
1.0-l背包问题是子集选取问题。
一般情况下，0-1背包问题是NP难题。0-1背包
问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类
似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当
右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余
物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右
子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后
依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是
右子树中解的上界。
2.解决办法思路：
为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考
察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
2.算法框架：
a.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
b.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
3.运用回溯法解题通常包含以下三个步骤：
a.针对所给问题，定义问题的解空间；
b.确定易于搜索的解空间结构；
c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
#include<iostream>

using namespace std;

class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );

public:
void print()
{

for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};

private:
int Bound(int i);
void Backtrack(int i);

int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解

};

int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}

void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子树
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}

}

class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}

private:
int ID;
float d;
};

int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//装入所有物品
//依物品单位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}

}

Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;

}

void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包问题——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"请输入背包容量(c)："<<endl;
cin>>c;
cout<<"请输入物品的个数(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;

cout<<"请输入物品的价值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];

cout<<"请输入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];

cout<<"最优解为(bestx)："<<endl;
cout<<"最优值为(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新开始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包问题
1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

#include <iostream.h>

struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};

int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;

void Init_good()
{
bag=new good [number];

for(int i=0; i<number; i++)
{
cout<<"请输入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"请输入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout<<endl;
}

}

int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}

*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}

void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界

for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志

if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}

}

void Display()
{

cout<<"可以放入背包的物品的编号为：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}