北邮算法作业贪心算法实验报告

《北邮算法作业贪心算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三次算法作业（贪心算法）姓名：吴迪班级：08211312学号：08211488班内序号15摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。备注：所有后缀为_ex的可执行文件为文件输入输出模式的程序，比如problem1_ex.exe（所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过Dev-C++编译器实际测试可以运行）problem1特殊的01背包（原算法分析题4-3）问题描述：01背包是在N件物品取出若干件放在空间为C的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P

2、1,P2……Pn，并取得最大价值。普通的01背包中物品的重量和价值没有明确的关系，这里定义一种特殊的01背包：向背包中放入的物品的价值和体积成反比，也就是价值越高，体积越小，注意这里物品价值和体积的乘积并不是固定值。例如：如下的物品满足这个“特殊的01背包”,5件物品:物品1,价值v=6,体积w=20物品2,价值v=1,体积w=60物品3,价值v=20,体积w=3物品4,价值v=15,体积w=15物品5,价值v=99,体积w=1假如我有一个容量为c的背包,c=20，那么选择物品3、4、5可以获得最大价值134。输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先

3、是两个正整数n和c，n代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物品的价值v和体积w。t的范围是(1-100),n的范围是(1-100000),c、v、w的范围不超过四字节的int型。输出：首先输出测试数据的组号，例如第一组的组号为“Case1:”，占一行。然后是一个整数，代表可以取得的最大价值，占一行。SampleInput:552062016020315159911110010051092171011093181093872610229613961889171061714086278331783110676846151954551

4、0378233753599109421535695169120396982285454110242676546SampleOutput:Case1:134Case2:0Case3:109Case4:212Case5:312问题分析:本题是特殊的01背包问题，由于其价值和重量的反比规律易证明贪婪算法的有效性，故本题可以采用贪心算法求解，即每次优选最轻物品也是最大价值物品。源代码：（仅附文件输入输出版本，标准输入输出版本见cpp代码文件）#include#includeusingnamespacestd;intgreedy_calcul

5、ate(int*v,int*w,constintn,constintc);intmain(){//inputintt;//testgroupnum1-100intn;//objectnum1-100000intc;//capacityint*v;int*w;fstreamin;fstreamout;in.open("problem1_input.txt",ios::in);out.open("problem1_output.txt",ios::out);in>>t;if(t>100

6、

7、t<1)out<<"errorinputoft!"<

8、i>n;if(n>100000

9、

10、n<1)out<<"errorinputofn!"<>c;if(c<=0)out<<"errorinputofc!"<>v[j];in>>w[j];}//outputout<<"Case"<

11、em("pause");return0;}intgreedy_calculate(int*v,int*w,constintn,constintc){unsignedintleast_weight=-1;intlw_num=0;intcount=0;inttotal_value=0;inttotal_weight=0;bool*x;x=newbool[n];for(inti=0;i