41背包问题的算法设计与实现完整.docx
《41背包问题的算法设计与实现完整.docx》由会员分享，可在线阅读，更多相关《41背包问题的算法设计与实现完整.docx（26页珍藏版）》请在冰点文库上搜索。
41背包问题的算法设计与实现完整
实验名称
背包问题的算法设计与实现
实验方案
实验成绩
实验日期
4月19日
实验室
信息系统设计与仿真室I
实验操作
实验台号
班级姓名
通信11-1BF王琳
实验结果
一、实验目的
1、掌握穷举法、递归法基本设计思想；
2、使用C语言实现背包问题的求解算法。
二、实验任务
1、从文件读取（或按格式输入）背包问题的测试数据；
2、设计背包问题的算法，用C语言实现算法求解；
3、输出背包问题的最优解。
三、问题描述
1、问题描述
01背包问题：
现有n种物品（每种物品不可再分），对1<=i<=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值最大。
2、解的描述
例如：
5种物品的解的表达形式：
{0,1,0,1,1}。
即第2,4,5种物品被选择装入背包。
1表示选入，0表示未选入。
四、穷举法设计
1、全局变量设计
#defineN5
intW=10;//最大载重
intw[N]={1,2,3,4,5};//各物品重量
intv[N]={5,4,3,2,1};//各物品价值
2、穷举法设计
算法思想：
穷举搜索所有可能的解，即2n种。
可用0~2n-1的二进制表示2n种解。
例如3的二进制从低到高位的表示{1,1,0,0,0}。
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
3、主函数设计
思路：
调用穷举法函数，接收返回的最优解，以二进制形式显示解，计算总价值并显示。
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
五、递归法设计
1、递归分析
n个物品重量不超过m的背包问题，可以递归为：
（1）若能放入第n个物品（m>=w[n]），则继续递归调用n-1物品不超过重量为m-w[n]的背包问题。
（2）若不放入第n个物品，则继续递归调用n-1物品不超过重量为m的背包问题。
（3）递归出口：
m=0，或n=0。
2、递归函数设计
算法思想：
按递归分析设计。
intx[N]={0};//记录解
intrecurse（intn,intm）
{
if（n==0||m==0）//出口
return0;
elseif（m>=w[n-1]&&recurse（n-1,m）{
x[n-1]=1;
returnrecurse（n-1,m-w[n-1]）+v[n-1];
}
else
{
x[n-1]=0;
returnrecurse（n-1,m）;
}
}
3、主函数设计
设计主函数，调用递归函数。
六、总结与讨论
1、问题与错误
不会二进制的转换，对于左右位移的算法也不会
递归还是不清楚思路过程
2、经验与收获
加深递归算法的应用
学习了穷举法，温习了二进制的转换
初步理解背包问题
3、改进与设想
七、源代码
#include
#defineN5
intW=10;
intw[N]={1,2,3,4,5};
intv[N]={5,4,3,2,1};
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
实验名称
背包问题的算法设计与实现
实验方案
实验成绩
实验日期
4
实验室
信息系统设计与仿真室I
实验操作
实验台号
81
班级姓名
通信11-1BF钟涛
实验结果
一、实验目的
1、掌握穷举法、递归法基本设计思想；
2、使用C语言实现背包问题的求解算法。
二、实验任务
1、从文件读取（或按格式输入）背包问题的测试数据；
2、设计背包问题的算法，用C语言实现算法求解；
3、输出背包问题的最优解。
三、问题描述
1、问题描述
01背包问题：
现有n种物品（每种物品不可再分），对1<=i<=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值最大。
2、解的描述
例如：
5种物品的解的表达形式：
{0,1,0,1,1}。
即第2,4,5种物品被选择装入背包。
1表示选入，0表示未选入。
四、穷举法设计
3、全局变量设计
#defineN5
intW=10;//最大载重
intw[N]={1,2,3,4,5};//各物品重量
intv[N]={5,4,3,2,1};//各物品价值
4、穷举法设计
算法思想：
穷举搜索所有可能的解，即2n种。
可用0~2n-1的二进制表示2n种解。
例如3的二进制从低到高位的表示{1,1,0,0,0}。
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
5、主函数设计
思路：
调用穷举法函数，接收返回的最优解，以二进制形式显示解，计算总价值并显示。
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
五、递归法设计
6、递归分析
n个物品重量不超过m的背包问题，可以递归为：
（4）若能放入第n个物品（m>=w[n]），则继续递归调用n-1物品不超过重量为m-w[n]的背包问题。
（5）若不放入第n个物品，则继续递归调用n-1物品不超过重量为m的背包问题。
（6）递归出口：
m=0，或n=0。
7、递归函数设计
算法思想：
按递归分析设计。
intx[N]={0};//记录解
intrecurse（intn,intm）
{
if（n==0||m==0）//出口
return0;
elseif（m>=w[n-1]&&recurse（n-1,m）{
x[n-1]=1;
returnrecurse（n-1,m-w[n-1]）+v[n-1];
}
else
{
x[n-1]=0;
returnrecurse（n-1,m）;
}
}
8、主函数设计
设计主函数，调用递归函数。
六、总结与讨论
1、问题与错误
不会用二进制显示最优解。
在加入物品时没有考虑到物品有没有超重，使程序运行不正确，在调用函数时没有给实参赋值。
2、经验与收获
通过本次试验我又学习到了用穷举法处理背包问题，同时再一次巩固了对递归调用的运用。
3、改进与设想
七、源代码
#include
#defineN5
intW=10;
intw[N]={1,2,3,4,5};
intv[N]={5,4,3,2,1};
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
实验名称
背包问题的算法设计与实现
实验方案
实验成绩
实验日期
4月19日
实验室
信息系统设计与仿真室I
实验操作
实验台号
班级姓名
通信11-1BF段思楠
实验结果
八、实验目的
1、掌握穷举法、递归法基本设计思想；
2、使用C语言实现背包问题的求解算法。
九、实验任务
1、从文件读取（或按格式输入）背包问题的测试数据；
2、设计背包问题的算法，用C语言实现算法求解；
3、输出背包问题的最优解。
一十、问题描述
1、问题描述
01背包问题：
现有n种物品（每种物品不可再分），对1<=i<=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值最大。
2、解的描述
例如：
5种物品的解的表达形式：
{0,1,0,1,1}。
即第2,4,5种物品被选择装入背包。
1表示选入，0表示未选入。
一十一、穷举法设计
1、全局变量设计
#defineN5
intW=10;//最大载重
intw[N]={1,2,3,4,5};//各物品重量
intv[N]={5,4,3,2,1};//各物品价值
2、穷举法设计
算法思想：
穷举搜索所有可能的解，即2n种。
可用0~2n-1的二进制表示2n种解。
例如3的二进制从低到高位的表示{1,1,0,0,0}。
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
3、主函数设计
思路：
调用穷举法函数，接收返回的最优解，以二进制形式显示解，计算总价值并显示。
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
一十二、递归法设计
1、递归分析
n个物品重量不超过m的背包问题，可以递归为：
（7）若能放入第n个物品（m>=w[n]），则继续递归调用n-1物品不超过重量为m-w[n]的背包问题。
（8）若不放入第n个物品，则继续递归调用n-1物品不超过重量为m的背包问题。
（9）递归出口：
m=0，或n=0。
2、递归函数设计
算法思想：
按递归分析设计。
intx[N]={0};//记录解
intrecurse（intn,intm）
{
if（n==0||m==0）//出口
return0;
elseif（m>=w[n-1]&&recurse（n-1,m）{
x[n-1]=1;
returnrecurse（n-1,m-w[n-1]）+v[n-1];
}
else
{
x[n-1]=0;
returnrecurse（n-1,m）;
}
}
3、主函数设计
设计主函数，调用递归函数。
一十三、总结与讨论
1、问题与错误
不会二进制的转换，对于左右位移的算法也不会
递归还是不清楚思路过程
2、经验与收获
加深递归算法的应用
学习了穷举法，温习了二进制的转换
初步理解背包问题
3、改进与设想
一十四、源代码
#include
#defineN5
intW=10;
intw[N]={1,2,3,4,5};
intv[N]={5,4,3,2,1};
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
实验名称
背包问题的算法设计与实现
实验方案
实验成绩
实验日期
4月19日
实验室
信息系统设计与仿真室I
实验操作
实验台号
班级姓名
通信11-1BF刘杨玉
实验结果
一、实验目的
1、掌握穷举法、递归法基本设计思想；
2、使用C语言实现背包问题的求解算法。
二、实验任务
1、从文件读取（或按格式输入）背包问题的测试数据；
2、设计背包问题的算法，用C语言实现算法求解；
3、输出背包问题的最优解。
三、问题描述
1、问题描述
01背包问题：
现有n种物品（每种物品不可再分），对1<=i<=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值最大。
2、解的描述
例如：
5种物品的解的表达形式：
{0,1,0,1,1}。
即第2,4,5种物品被选择装入背包。
1表示选入，0表示未选入。
四、穷举法设计
1、全局变量设计
#defineN5
intW=10;//最大载重
intw[N]={1,2,3,4,5};//各物品重量
intv[N]={5,4,3,2,1};//各物品价值
2、穷举法设计
算法思想：
穷举搜索所有可能的解，即2n种。
可用0~2n-1的二进制表示2n种解。
例如3的二进制从低到高位的表示{1,1,0,0,0}。
intexhaust（）
{
intmax=（2<intn;
intbest=0;//记录最大总价值
intsol=0;//记录最优解
for（n=0;n{
intp=0,m=0;//p记录当前解的总价值,m表示当前解的总重量
intx=n,i=0;
while（x!
=0）
{
intbit=x&1;//取当前解的二进制位
if（bit）//bit==1,选入
{
m=m+w[i];
p=p+v[i];
}
i++;
x=x>>1;//右移1位
}
if（m<=W&&p>best）{//总重量不超过W,且总价值更大
best=p;//更新最大总价值
sol=n;//更新最优解
}
}
returnsol;//返回最优解
}
3、主函数设计
思路：
调用穷举法函数，接收返回的最优解，以二进制形式显示解，计算总价值并显示。
voidmain（）
{
inti,sol,best=0;
sol=exhaust（）;
for（i=0;iprintf（"%d",sol%2）;
if（sol%2）
best=best+v[i];//计算解的总价值
}
printf（"\n"）;
printf（"%d\n",best）;//显示总价值
}
五、递归法设计
1、递归分析
n个物品重量不超过m的背包问题，可以递归为：
（1
升级会员 