1、算法综合实验报告学号：1004121206姓名： 林一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解 ， 并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证 。
二、程序设计的基本思想、原理和算法描述：1、蛮力法1.1 数据结构注：结构体obj用来存放单个物品的价值和重量typedef struct objint w;
物品的重量in t v;
/物品的价值;
1.2 函数组成void subset(i nt s10,i nt n):用来生成子集的函数void judge(i nt s10, obj obj,i nt mark,i nt n,i nt c):判断子集 。

2、的可行性in t getmax(i nt mark,i nt n,i nt &flag):求解问题的最优解void outputObj(i nt flag, int s10,i nt n):输出选择物品的情况1.3 输入/输出设计本程序通过键盘进行输入、屏幕进行输出1.4符号名说明符号说明S存放子集mark记录子集的可行性n物品的个数c物品的容量max记录背包所能产生的最大价值flag记录能产生最大价值的子集的编号1.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量wn,价值vn 输出：装入背包的物品编号以及产生的最大价值1. 初始化最大价值 max=O,结果子 。

3、集s= ;
2. 对集合1,2,n的每一个子集T,执行下述操作：2.1 初始化背包的价值v=0 ， 背包的重量w=0;
2.2 对子集t的每一个元素j2.2.1 女口果w+wjvc,贝U w=w+wj,v=v+vj;
2.2.2 否则 ， 转步骤2考察下一个子集；2.3 如果 maxc )4.1 将第 i 个物品放入背包 ,objecti.Num=1 ；4.2 c-=pron.Weight ；4.3 i+ ；5. 记录最后放入背包的物品的重量： objecti.Num=(double)C/objecti.Weight ；4、分支限界法4.1 数据结构 注：物品结构体 ， 存放物品价值、重量、单位价值、物品编号等 。

4、信息 struct objint v;
/物品价值int w;
/物品重量double avg;
/ 物品单位价值int id;
/ 物品编号;
注：结构体 node 用来存放节点表节点struct nodenode *parent,/父亲结点指针*next;
/后继结点指针int level,/ 节点所处的层isin,/记录物品是否装入背包 ，0 代表不装 ,1 代表装入cw,/当前背包已经装入的物品重量cv;
/当前背包已经装入的物品价值double ub;
/ 结点的上界值;
4.2 函数组成int Partitio n(_Object r,i nt first,i nt en d);
以数组第一个元素为准 。

5、对数组进行一次划分并返回基准元素的位置坐标void QuickSort(_Object r,i nt first, int en d);
快速排序double Upb(i nt i,i nt cw,i nt cv);
计算上界值node *nnoder(node * pare nt1,i nt isin 1,double ub1);
生成一个新的结点void add node( node *n ode1);
将结点添加到队列中node *n ext no de();
/取下一个结点void fen zjx();
/分支界限法的主要实现函数void output();
/4.3输入/输出设计用于输出物品的选 。

6、择情况及最优解本程序通过键盘进行输入、屏幕进行输出4.4符号名说明符号说明c背包的容量n物品的个数pro存放物品信息avg物品的单位价值量opv背包容量最优解popv指向最优解的指针level节点的层cw当前背包装载量cv当前背包价值ub节点的上界值isin记录当前结点物品是否放入背包flag物品原来位置(4) 算法描述 算法的伪代码描述如下： 输入：背包的容量 c, 物品的个数 n,n 个物品的信息 pron 输出：装入背包的物品标号和背包获得的最大价值1. 对输入的物品按照单位价值量递减的顺序进行排序2. 初 始 化 问 题 最 优 解 opv=0, 初 始 化 第 0 层 结 点，计 。

7、 算 上 界 值 ub=Upb(0,0,0);
并设置该结点设为优先级队列的根结点3. 循环直到优先级队列为空3.1 如果取出当前结点位于第 n-1 层 ， 则其子结点已是叶子结点 ，判断子结点取值情况 ， 若得到的解大于当前问题得到的最优解opv,贝皿置问题的最优解 opv3.2 如果取出当前结点层 level #include using namespace std；/ 物品typedef struct obj int w； int v；/ 生成子集void subset(int s10,int n)int i,j,m,k;
for(i=0;
i=0;
j-)m=k%2;
sij=m;
k=k/2;
/ 判 。

8、断子集可行性void judge(int s10, obj obj,int mark,int n,int c) int i,j,v,w;
for(i=0;
imax)max=marki;
flag=i;
return max;
/ 输出选择物品的情况void outputObj(int flag,int s10,int n)coutc;
coutn;
coutobji.w;
coutobji.v;
subset(s,n);
judge(s,obj,mark,n,c);
max=getmax(mark,n,flag);
outputObj(flag,s,n);
coutusing namespace std;
/ 比较并返 。

9、回两个数中的较大值int max(int i,int j)if(i0;
i-)/if(VijVi-1j)xi=1;
j=j-wi;
else xi=0;
return Vnc;
int main()int c,n,w105,v105,x105,max;
/xcoutc;
coutn;
coutwi;
coutvi;
max=KnapSack(w,v,x,n,c);
cout#includeusing namespace std;
/ 物品结构体struct _Objectint Value;
/ 物品价值int Weight;
/ 物品重量double AveValue;
/ 物品单位价值double Num;
/ 物品可以 。

10、放入的数量int key;
/ 物品标号;
/ 划分int Partition(_Object r,int first,int end)int i=first,j=end;
while(irj.AveValue)j-;
if(irj.AveValue)i+;
if(ic;
coutn;
coutproi.Weightproi.Value;
proi.AveValue=https://www.renrendoc.com/paper/(double)proi.Value/proi.Weight;
proi.Num=0;
proi.key=i;
QuickSort(pro,0,n-1);
double maxValue=https://www.renrendoc.com/paper/knaspsack(n,c,pro);
cout #inclu 。

11、de #include #include #include using namespace std;
/ 物品结构体struct obj int v;
/物品价值int w;
/物品重量double avg;
/ 物品单位价值int id;
/物品编号;
/ 节点结构体struct nodenode *parent,/ 父亲结点指针*next;
/ 后继结点指针int level,/ 节点所处的层isin,/记录物品是否装入背包 ，0 代表不装 ,1 代表装入cw,/当前背包已经装入的物品重量cv;
/当前背包已经装入的物品价值double ub;
/ 结点的上界值;
/ 划分int Partition(obj。

12、r,int first,int end)int i=first,j=end;
while(irj.avg)j-;
if(irj.avg) i+;
if(inext=NULL;
opv=0;
popv=new node1;
popv=NULL;
QuickSort(pro,0,n-1);
fzjx:fzjx()deletefirst;
deletefront;
deletepopv;
deletepro;
double fzjx:Upb(int i,int cw,int cv)int cleft=c-cw;
double v=(double)cv;
if (iparent=parent1;
node2-next=NULL;
。

13、 node2-level=(parent1-level)+1;
node2-isin=isin1;
node2-ub=ub1;
if(isin1=1) node2-cw=parent1-cw+proparent1-level.w;
node2-cv=parent1-cv+proparent1-level.v ;
elsenode2-cw=parent1-cw;
node2-cv=parent1-cv;
return(node2);
void fzjx:addnode(node *node1)/ 将结点加入优先队列node *p=front-next,*next1=front;
double ub=node 。

【蛮力法动归|蛮力法动归贪心分支限界法解01背包问题】14、1-ub;
while(p!=NULL)if(p-ubnext=p;
next1-next=node1;
break;
next1=p;
p=p-next;
if(p=NULL)next1-next=node1;
node * fzjx:nextnode()/ 取上限最大结点node *p=front-next;
front-next=p-next;
return(p);
void fzjx:fenzjx()int i;
double ub2;
node *node3;
first=new node1;
/根结点first-parent=NULL;
first-next=NULL;
first-level=0;
。

15、first-cw=0;
first-cv=0;
first-isin=0;
ub2=Upb(0,0,0);
first-ub=ub2;
front-next=first;
while(front-next!=NULL)node3=nextnode();
i=node3-level;
if(i=n-1)if(node3-cw+proi.wcv+proi.v)opv)opv=node3-cv+proi.v;
popv=nnoder(node3,1,opv);
if(node3-cv)opv)opv=node3-cv;
popv=nnoder(node3,0,opv);
if(icw+proi.wcw+proi 。

16、.w,node3-cv+proi.v)opv) ub2=Upb(i,node3-cw+proi.w,node3-cv+proi.v);
addnode(nnoder(node3,1,ub2);
ub2=Upb(i,node3-cw,node3-cv);
if(ub2opv)addnode(nnoder(node3,0,ub2);
void fzjx:output()int i;
for(i=n-1;
i=0;
i-)flagproi.id=popv-isin;
popv=popv-parent;
coutc;
coutn;
pro1 = new objn;
coutpro1i.wpro1i.v;
pro1i.avg= 。

17、1.0*pro1i.v/pro1i.v;
pro1i.id=i;
fzjx fzjx(pro1,c,n);
fzjx.fenzjx();
fzjx.output();
return 0;
四、运行输出结果：1、蛮力法用例测试 1 ：用例测试2 :*E;
Debiig01ba Banli. cze85Bu n 刀tl 值为值an 价 c 甘里数的的编大t 容个品品的最y 的的物物口旳的ke 包口艮人物舸卩 菲鸟输書容細 一入入乳杀背可ff i务入包 一 冃P?41522、动态规划法用例测试1 :*C：kProer& FdlesVlicrosoft Visual SiudioMyPrcjjectslinDe 。

18、bugl135量值为值Dn :童Q A C 量数的能编大to 重个品品最y 的的韧物|的蛇 包口 B,m入入的纳y 4厕層勺容an 人弓可、1可S 刀分人包 隹焉隹侷佳輛隹冃F1用例测试2 :3、贪心法用例测试1:用例测试2:4、分支限界法用例测试1 :! 5 i 值畫： 价丄是 和：值 匚各 :;
重号大 =编r 谷个品品的口的鬲生 巴口 X的产 遇豐r A.- 可入包rocess returned 0 0x0) execution tue : 20.1? s ress emu keu to continue用例测试2 :五、调试和运行程序过程中产生的问题及采取的措施：1问题：蛮力法解决0/1 。

19、背包问题时 ， 如何表示给定物品集合的所有子集 解决办法：可以借用“二进制” ， 将第i个子集的下标i使用二进制表示 ， 对应的二 进制各位的数字（0,1 ）表示相应编号的物品是否包含在该子集中；eg 0101 ， 表示子集2,4等等2、 问题：贪心法解决0/1背包问题时 ， 再对物品按照单位价值递减排序后 如何记录输入时物品的顺序解决办法：可以在表示物品的结构体中增加属性 key ， 在输入时就记录下物品的编号3、问题：分支界限法解决 0/1背包问题时 ， 如何能快速的选取目标函数值 取得极大的结点解决办法：可以采用优先级队列的存取结构存放结点 ， 每次都选取队列的队首元素即满足该结点目标函数值取得极大六、对算法的程序的讨 。

20、论、分析 ， 改进设想 ， 其它经验教训：1.在用蛮力法解决 0/1 背包问题时 ，为了解决将物品按照单位价值量递减的 顺序排序后 ，物品在输出时还能保证原来的顺序 ，虽然通过在输入时就为每个物 品添加编号可以解决问题 ，但同时增大了解决问题的时间开销 ，只问了匹配物品 序号 ， 时间开销就达到Q( n*n),这不是解决问题的简单方式 ， 不妨利用分支界 限法处理该问题的方式 ，通过设置一个数组来记录 ，增大了空间开销 ，换取了时 间上的节约 。
2、通过比较蛮力法、动态规划法、贪心法、分支界限法四种方法来解决0/1问题 ， 可以发现 ，蛮力法设计思想简单 ，对于输入规模较小时可以快速的得到问 题的最优解；当规模增大时 ， 时间开销将达到指数级；同样 ， 动态规划法所需的 的时间开销迅速增大 ， 用于存放迭代结果的二维数组 Vnn 的计算时间延长 ，增大了时间开销；贪心法和分支界限法都涉及要对输入物品的顺序按照单位价值 量递减进行排序的问题 ，采用不同的排序算法会影响算法的执行速度 ，为了保证 物品的顺序不变 ，不同的策略也会产生不同的效果 ，分支界限法在最坏情况下等 同于蛮力法的时间开销； 贪心法只适用于可以全部或部分的装入物品 ，而对于只 限于装入和不装入两种状态 ，则不能满足问题的要求 ，但是可以将贪心法用于计 算分支界限法的下线 ，这样就可以更加有效地对解空间进行剪枝 ，降低时间开销 。

稿源：(未知)

【傻大方】网址：/a/2021/0801/0023374259.html

标题：蛮力法动归|蛮力法动归贪心分支限界法解01背包问题