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

第三次算法作业（贪心算法）

姓名：吴迪

班级学号班内序号15

摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。

（所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过Dev-C++编译器实际测试可以运行）

problem1

特殊的01背包（原算法分析题4-3）

问题描述：01背包是在N件物品取出若干件放在空间为C的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,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,代表测试数据的组数。每组测试数据首先是两个正整数n和c，n代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物品的价值v和体积w。t的范围是(1-100),n的范围是(1-100000),c、v、w的范围不超过四字节的int型。

输出：首先输出测试数据的组号，例如第一组的组号为“Case1:”，占一行。然后是一个整数，代表可以取得的最大价值，占一行。

SampleInput:

5

520

620

160

203

1515

991

11

100100

510

9217

10110

9318

1093

8726

1022

9613

9618

8917

1061

7140

8627

8331

7831

1067

6846

1519

5455

1037

8233

7535

9910

9421

5356

9516

9120

3969

8228

5454

1102

4267

6546

SampleOutput:

Case1:

134

Case2:

0

Case3:

109

Case4:

212

Case5:

312

问题分析:

本题是特殊的01背包问题，由于其价值和重量的反比规律易证明贪婪算法的有效性，故本题可以采用贪心算法求解，即每次优选最轻物品也是最大价值物品。

源代码：（仅附文件输入输出版本，标准输入输出版本见cpp代码文件）

#includeiostream

#includefstream

usingnamespacestd;

intgreedy_calculate(int*v,int*w,constintn,constintc);

intmain()

{

//input

intt;//testgroupnum1-100

intn;//objectnum1-100000

intc;//capacity

int*v;

int*w;

fstreamin;

fstreamout;

in.open(problem1_input.txt,ios::in);

out.open(problem1_output.txt,ios::out);

int;

if(t100||t1)

outerrorinputoft!endl;

for(inti=0;it;i++){

inn;

if(n100000||n1)

outerrorinputofn!endl;

inc;

if(c=0)

outerrorinputofc!endl;

v=newint[n];

w=newint[n];

for(intj=0;jn;j++)

{

inv[j];

inw[j];

}

//output

outCasei:endl;

outgreedy_calculate(